Домашнее задание на тему «Основы математической логики. Логические операции»

Тема: «Основы математической логики. Логические операции»

Автор работы: Федотова К.А., преподаватель

Пояснительная записка

Учебные пособия и задачники в основном насыщены задачами-приказами, направленными на выполнение каких-либо конкретных действий. В силу данного факта акцент делается в основном на освоение учащимися лишь технических навыков. Поэтому особое внимание я стараюсь уделять заданиям на основе технологии укрупнения дидактических единиц П.М. Эрдниева. В рамках работы с укрупнённой дидактической единицей учащиеся поимо выполнения стандартных заданий, основанных лишь на имеющихся у них знаниях, выполняют целый перечень действий, родственных действиям математика-исследователя, а именно: самостоятельной формулируют задачи, работают с аналогичными задачами, с взаимообратными утверждениями, получают обобщения многих математических фактов.

В алгебре логики исследования тесно связаны с понятием высказывания. Однако не рассматривается конкретное содержание высказывания, важным является только факт его истинности или ложности.

Целью выполнения данного домашнего задания является формирование представлений об алгебре высказываний и основных логических операциях, формирование навыка построения таблиц истинности различных логических операций.

Домашнее задание предназначено для обучающихся первого курса по специальностям 09.02.01. Компьютерные системы и комплексы и 09.02.07. Информационные системы и программирование.

Данное задание можно выполнять как индивидуально, так и в группе. Возможна следующая реализация работы с данными заданиями: группа обучающихся разбивается на три команды. Одной команде предлагаются задачи 1-3, связанные с конъюнкцией, второй – задачи 1-3 для дизъюнкции, третьей – для импликации. Время на выполнение данного домашнего задания установить довольно сложно, поскольку каждый обучающийся работает в своем темпе.

Проверку правильности выполнения заданий необходимо осуществить в начале следующего занятия в процессе фронтального обсуждения.

В данной работе представлены задания и примерный принцип их решения.

Задача 1. Заполните таблицу 1 истинности для логической операции конъюнкции

Таблица 1 – Исходная таблица для задачи 1

Решение. Мы видим, что варианты истинности и ложности высказываний и расположены не в стандартном порядке.

По определению логической операции конъюнкции, имеем, что составное высказывание, полученное в результате операции логического умножения истинно тогда и только тогда, когда истинны все входящие в него простые высказывания (таблица 2)

Таблица 2 – Таблица истинности

Задача 2. Часть таблицы истинности для конъюнкции нечаянно стёрли с доски, так что осталась таблица 3.

Таблица 3 – Исходная таблица для задачи 2

Восстановите таблицу истинности. Сколько решений имеет задача?

Решение. Последний столбец должен быть заполнен нулями по определению конъюнкции. Получаем таблицу 4.

Таблица 4 – Промежуточные результаты решения задачи 2

По той же причине вторая строка должна быть заполнена единицами, поскольку составное высказывание, полученное в результате логического умножения истинно тогда и только тогда, когда оба простых высказывания являются истинными. Таким образом, получаем таблицу 5.

Таблица 5 – Промежуточные результаты решения задачи 2

В клетке должен стоять 0, так как нам известно, что простое высказывание истинно, и следовательно составное высказывание является истинным тогда и только тогда, когда простое высказывание будет ложным (таблица 6).

Таблица 6 – Промежуточные результаты решения задачи 2

Остаток первого столбца заполняем 0, поскольку простое высказывание в данном случае может принимать в двух случаях истинные значения, а в двух других – ложные. В результате выполнения данной последовательности действий, получим таблицу истинности (таблица 7)

Таблица 7 – Промежуточные результаты решения задачи 2

В двух оставшихся клетках может стоять либо пара , либо пара . Таким образом, задача имеет два решения.

Первое решение имеет вид, представленный в таблице 8.

Таблица 8 – Первое решение задачи 2

Второе решение имеет вид, представленный в таблице 9.

Таблица 9 – Второе решение задачи 2

Задача 3. Часть таблицы истинности для логической операции конъюнкция нечаянно стёрли с доски, так что осталась таблица 10.

Таблица 10 – Исходная таблица для задачи 3

Восстановить таблицу истинности. Сколько решений имеет данная задача?

Решение. По определению конъюнкции последний столбец должен быть заполнен нулями, а третья строка – единицами. В результате получаем таблицу 11.

Таблица 11 – Промежуточные результаты решения задачи 3

Теперь необходимо разместить три пары , и по трём незаполненным строкам. Вариантов таких размещений всего 6. Действительно, пару можно поместить в одну из трёх строк: первую, вторую или четвёртую. Если выбрать одну из строк, то вторую пару можно поместить в одну из двух оставшихся строк. Местоположение третьей пары определяется однозначно.

Данное решение можно отобразить с помощью графа (рис. 1):

Рис.1. Граф решений для задачи 3

Задача 4. Сформулируйте и решите задания, аналогичные заданиям 1-3 для дизъюнкции.

Наводящее соображение. Вероятно, что значение «истина» играет особую роль для логической операции конъюнкции, потому что встречается только один раз в последнем столбце таблицы истинности. Для дизъюнкции такую роль играет значение «ложь».

Формулировка задания 4.1. Заполните таблицу истинности для логической операции дизъюнкции (таблица 12).

Таблица 12 – Исходная таблица для задачи 4.1

Решение. Мы видим, что варианты истинности и ложности высказываний и расположены не в стандартном порядке.

По определению логической операции дизъюнкции, имеем, что составное высказывание, полученное в результате операции логического сложения истинно тогда и только тогда, когда истинно хотя бы одно из входящих в него простых высказываний (таблица 13).

Таблица 13 – Результат решения задачи 4.1

Формулировка задания 4.2. Часть таблицы истинности для дизъюнкции нечаянно стёрли с доски, так что осталась таблица 14.

Таблица 14 – Исходная таблица для задачи 4.2

Восстановите таблицу истинности. Сколько решений имеет задача?

Решение. Последний столбец должен быть заполнен единицами по определению дизъюнкции. Получим таблицу 15.

Таблица 15 – Промежуточные результаты решения задачи 4.2

По той же причине третья строка должна быть заполнена нулями, поскольку составное высказывание, полученное в результате операции логического сложения ложно только в том случае, когда оба входящих в него простых высказывания являются ложными. Таким образом, получаем таблицу 16.

Таблица 16 – Промежуточные результаты решения задачи 4.2

В клетке должна стоять 1, так как нам известно, что простое высказывание ложно, и следовательно составное высказывание является истинным тогда и только тогда, когда простое высказывание будет истинным. Получаем таблицу 17.

Таблица 17 – Промежуточные результаты решения задачи 4.2

Остаток первого столбца заполняем 1, поскольку простое высказывание в данном случае может принимать в двух случаях истинные значения, а в двух других – ложные. В результате выполнения данной последовательности действий, получим таблицу 18.

Таблица 18 – Промежуточные результаты решения задачи 4.2

В двух оставшихся клетках может стоять либо пара , либо пара . Таким образом, задача имеет два решения.

Первое решение имеет вид, представленный в таблице 19.

Таблица 19 – Первое решение задачи 4.2

Второе решение имеет вид, представленный в таблице 20.

Таблица 20 – Второе решение задачи 4.2

Формулировка задания 4.3. Часть таблицы истинности для логической операции дизъюнкции нечаянно стёрли с доски, так что осталась таблица 21.

Таблица 21 – Исходная таблица для задачи 4.3

Восстановить таблицу истинности. Сколько решений имеет данная задача?

Решение. По определению дизъюнкции последний столбец должен быть заполнен единицами, а вторая строка – нулями. В результате получаем таблицу 22.

Таблица 22 – Промежуточные результаты решения задачи 4.3

Теперь необходимо разместить три пары , и по трём незаполненным строкам. Вариантов таких размещений всего 6. Действительно, пару можно поместить в одну из трёх строк: первую, третью или четвёртую. Если выбрать одну из строк, то вторую пару можно поместить в одну из двух оставшихся строк. Местоположение третьей пары определяется однозначно.

Данное решение можно отобразить с помощью графа (рис. 2):

Рис.2. Граф решений для задачи 4.3

Задача 5. Сформулируйте и решите задания, аналогичные заданиям 1-3 для импликации.

Наводящее соображение. Импликация похожа на конъюнкцию и дизъюнкцию в том отношении, что в последнем столбце таблицы истинности одно значение истинности встречается трижды, а другое значение – только один раз.

Формулировка задания 5.1. Заполните таблицу истинности для логической операции импликации (таблица 23).

Таблица 23 – Исходная таблица для задачи 5.1

Решение. Мы видим, что варианты истинности и ложности высказываний и расположены не в стандартном порядке.

По определению логической операции импликации, имеем, что составное высказывание, полученное в результате операции логического следования ложно тогда и только тогда, когда из истинного высказывания следует ложное. Таким образом, получаем таблицу истинности (таблица 24).

Таблица 24 – Результат решения задачи 5.1

Формулировка задания 5.2. Часть таблицы истинности для импликации нечаянно стёрли с доски, так что осталась таблица 25.

Таблица 25 – Исходная таблица для задачи 5.2

Восстановите таблицу истинности. Сколько решений имеет задача?

Решение. Последний столбец должен быть заполнен единицами по определению импликации. Получаем таблицу 26.

Таблица 26 – Промежуточные результаты решения задачи 5.2

По той же причине вторая строка должна быть заполнена парой соответственно, поскольку составное высказывание, полученное в результате операции логического следования ложно тогда и только тогда, когда из истинного высказывания следует ложное. Таким образом, получаем таблицу 27.

Таблица 27 – Промежуточные результаты решения задачи 5.2

В клетке может стоять как 0, так и 1, поскольку и в том, и другом случае сложное высказывание, полученное в результате операции импликации будет истинным. Получаем две таблицы (таблицы 28, 29).

Таблица 28 – Промежуточные результаты решения задачи 5.2

Таблица 29 – Промежуточные результаты решения задачи 5.2

Теперь необходимо разместить пары и по двум незаполненным строкам таблицы 28. Вариантов таких размещений всего 2. Действительно, пару можно поместить в одну из двух строк: третью или четвёртую. Местоположение второй пары определяется однозначно.

Таким образом, получаем первое решение, которое представлено в таблице 30.

Таблица 30 – Первое решение задачи 5.2

Второе решение представлено в таблице 31.

Таблица 31 – Второе решение задачи 5.2

Теперь необходимо разместить пары и по двум незаполненным строкам таблицы 29. Вариантов таких размещений всего 2. Действительно, пару можно поместить в одну из двух строк: третью или четвёртую. Местоположение второй пары определяется однозначно.

Таким образом, получаем третье решение, которое представлено в таблице 32.

Таблица 32 – Третье решение задачи 5.2

Четвёртое решение представлено в таблице 33.

Таблица 33 – Четвёртое решение задачи 5.2

Формулировка задания 5.3. Часть таблицы истинности для логической операции импликации нечаянно стёрли с доски, так что осталась таблица 34.

Таблица 34 – Исходная таблица для задачи 5.3

Восстановить таблицу истинности. Сколько решений имеет данная задача?

Решение. По определению импликации последний столбец должен быть заполнен единицами, а последняя строка – парой . В результате получаем таблицу 35.

Таблица 35 – Промежуточные результаты решения задачи 5.3

Теперь необходимо разместить три пары , и по трём незаполненным строкам. Вариантов таких размещений всего 6. Действительно, пару можно поместить в одну из трёх строк: первую, вторую или третью. Если выбрать одну из строк, то вторую пару можно поместить в одну из двух оставшихся строк. Местоположение третьей пары определяется однозначно.

Данное решение можно отобразить с помощью графа (рис. 3):

Рис.3. Граф решений для задачи 5.3