Составление таблиц истинности логических функций.

Каждая логическая функция логических переменных имеет таблицу истинности – значения этой функции в зависимости от значений её переменных.

Так, например, в предыдущем пункте мы познакомились с тремя логическими функциями:
a)f(p,q)= p Ú q; b)g(p,q)= p Ù q; и c)h(p,q)= pÞq
и с их таблицами истинности, каждая из которых содержала 4 строки – 4 возможных комбинации значений p и q.
Упражнение №3.

Сколько строк содержит таблица логической функции от трёх переменных? От четырёх?

Составим таблицу истинности для функции f(p,q)=Ø(pÚØq)ÙØp. Поскольку последней выполняется конъюнкция, а она истинна только тогда, когда оба её операнда истинны, то Øp и Ø(pÚØq) должны быть оба истинны. Это означает, что р и pÚØq должны быть оба ложны. Чтобы дизъюнкция была ложной оба её операнда должны быть ложны, а поскольку р уже ложно, то ложным должен быть Øq, т.е., q должно быть истинно.

Итак, в таблице истинности для нашей функции только в строчке, соответствующей значению «р ложно, а q истинно» функция принимает значение Истина, а в остальных строчках –Ложь:

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

Например, очевидно, эквивалентными являются функции pÚq и qÚp, pÙq и qÙp (свойство коммутативности для дизъюнкции и конъюнкции), а также pÚ(qÚr) и (pÚq)Úr;

pÙ(q Ùr) и (pÙq)Ùr ((свойство ассоциативности для дизъюнкции и конъюнкции).

Для обозначения эквивалентности будем использовать символ ~.

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

а) (pÚØq)Þ(qÙØp) e) (pÙØqÙØr) Ú (ØpÙqÙr)

b) Ø(qÙØp)Þ(ØpÚq) f) (ØpÞq)Þ(ØrÞp)

c) (ØqÙp)Ú(qÙØp) g) (pÙqÙØr)Ú(ØpÙØqÙr) Ú (pÙØqÙØr)

d) (ØqÞ(qÙØp))Ùp h) (pÙqÙØr)Þ(ØpÙØqÙr)

Упражнение 5.
Среди следующих логических функций найдите пары эквивалентных:

a) F, T, p, ØØp, pÚF, pÚT, pÙF, pÙT, рÙp, pÚp, pÚØp, pÙØp

b) Ø(pÙq), Ø(pÚq), ØpÚØq, ØpÚq, ØpÙØq, pÞq, pÚ(pÙq), pÙ(pÚq), Øq ÞØp,

c) pÚ(rÙq), pÙ(rÚq), (pÙr)Ú(pÙq), (pÚr)Ù(pÚq) , (p Ùq)Ú(Øp ÙØq),
(pÞq) Ù(qÞp)

Комментарии. Функция (pÞq) Ù(qÞp) истинна тогда, когда р и q принимают одни и те же значения – оба ложны или оба истинны. То есть, когда р и q эквивалентны. Вместо простых логических переменных можно было бы поставить составные, сложные формулы (логические функции) зависящие от нескольких переменных и результат был бы тот же. (АÞВ) Ù(ВÞА): Формула А верна тогда и только тогда, когда верна формула В; формулы А и В истинны или ложны одновременно. Пишут также АÛВ, что равносильно А~В.

В упражнении 5b одна из найденных вами эквивалентностей служит обоснованием метода доказательства «от противного». Предположим, что мы хотим доказать, что из А следует В. Мы предполагаем, что В ложно и приходим к выводу, что тогда и А ложно. Отсюда делаем вывод, что на самом деле В истинно.

Какой именно эквивалентности соответствует это рассуждение?

Упражнения 4е и 4g помогают решить следующую, обратную к упражнению 4 задачу: построить логическую функцию (формулу) с заданной таблице истинности.

Дело в том, что функция, которая истинна только при данной комбинации значений логических переменных – это конъюнкция тех из этих переменных, значения которых «Т» и отрицаний тех из них, значения которых «F».

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

Соглашение: принято считать, что порядок выполнения действий в логических формулах такой: вначале выполняются все конъюнкции, потом дизъюнкции. Поэтому можно, например, в выражении (pÙr)Ú(pÙq) скобки опустить.

Упражнение 6.
Построить логические функции трёх переменных со следующими таблицами истинности:

Замечание. Так как для каждой таблицы истинности можно построить логическую функцию из дизъюнкции конъюнкций, то для любой логической функции существует эквивалентная ей, имеющая форму дизъюнкции конъюнкций – она так и называется: дизъюнктивная нормальная форма, сокращённо д.н.ф.

Таблица основных логических тождеств. Двойственность. Вывод новых тождеств с помощью основных.

Результаты упражнений 5 вместе с замечаниями перед упражнениями 4 позволяют свести в таблицу сводку основных логических тождеств (эквивалентных формул):

Таблица наглядно демонстрирует двойственность, характеризующую исчисление высказываний: если заменить в левой колонке таблицы значки Ùна Úа истину на ложь и наоборот, то обнаружим полученное новое (верное) утверждение в правой колонке таблицы. Так что «учить» придётся только половину таблицы.

Но и запоминать специально эти тождества не придётся: мы просто применяем эту таблицу при упрощении логических выражений, имея её всегда под рукой, так что, в конце концов, она запомнится непроизвольно.

Проиллюстрируем на примере, как, применяя тождества из этого списка можно доказывать другие тождества. Докажем, что формула ((pÞq)Ù(qÞr))Þ(pÞr) является тавтологией (т.е. истинна при всех значениях переменных p, q, r.).

Читается эта логическая функция так: если из p следует q и из q следует r, то из p следует r. (свойство транзитивности импликации).

Сначала применим 2 ко всем внутренним импликациям:

((ØpÚq)Ù(ØqÚr))Þ(ØpÚr)

Теперь заменим внешнюю импликацию:

Ø((ØpÚq)Ù(ØqÚr))Ú(ØpÚr)

К левой части дизъюнкции применяем 16 а в правой опускаем скобки:

Ø(ØpÚq)ÚØ(ØqÚr))ÚØpÚrПрименяем 17 к каждой скобке:

ØØpÙØqÚØØqÙØrÚØpÚrПрименяем 1:

pÙØqÚqÙØrÚØpÚrПрименяем 17: Øp~ØpÚ(ØpÙØq); r~rÚ(rÙq)

pÙØqÚqÙØrÚØpÚ(ØpÙØq)ÚrÚ(rÙq)Применяем 10 и 9:

pÙØqÚØpÙØqÚqÙØr ÚqÙrÚØpÚrПрименяем 13:

( pÚØp)ÙØq Ú qÙ(ØrÚr)ÚØpÚrПрименяем 7:

ТÙØqÚqÙТÚØpÚrПрименяем 3:

ØqÚqÚØpÚrСнова применяем 7:

ТÚØpÚr и, наконец, дважды применяя 3, получим Т.