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

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

Так, например, в предыдущем пункте мы познакомились с тремя логическими функциями: 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 истинно» функция принимает значение Истина, а в остальных строчках –Ложь:

p	q	(pq)p
T	T	F
T	F	F
F	T	T
F	F	F

Логические функции, которые принимают значение 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. Среди следующих логических функций найдите пары эквивалентных:

1. F, T, p, ØØp, pF, pT, pF, pT, рÙp, pÚp, pÚØp, pÙØp

2. Ø(pÙq), Ø(pÚq), ØpÚØq, ØpÚq, ØpØq, pÞq, pÚ(pq), p(pÚq), Øq ÞØp,

3. 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. Построить логические функции трёх переменных со следующими таблицами истинности:

Значения переменных			Значения функций
p	q	r	f	g	h
T	T	T	T	F	F
T	T	F	F	F	F
T	F	T	F	F	T
T	F	F	F	T	F
F	T	T	F	T	T
F	T	F	F	F	F
F	F	T	F	F	T
F	F	F	T	F	F

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