М. С. Спирина - Учебно-методическое пособие по дисциплине «Математическая логика и теория алгоритмов» для студентов технических направлений и специальностей

высказываний
Занятие №2. Логика предикатов. Логическое следование
Раздел 2. Формальные теории
Занятие № 3. Аксиоматические системы. Формальный вывод
Занятие №4. Исчисление высказываний
Занятие № 5. Исчисление предикатов
Раздел 3. Элементы теории алгоритмов
Занятие № 6. Формализация понятия алгоритма. Рекурсивные функции. Машина
Тьюринга
Раздел 4. Элементы нечеткой логики
Занятие № 7-8. Основы нечеткой логики
Раздел 1. Построение логических исчислений
Занятие №1. Логика высказываний
Совершенные и минимальные формы. Формула F называется тавтологией, если
самый правый из столбцов таблицы истинности – столбец значений, содержит единицы
(истина), и только единицы. Обозначение тавтологии: |= F.
Теорема. Критерий тождественно истинной формулы алгебры логики:
Для того чтобы формула логики высказываний была тавтологией, необходимо и
достаточно, чтобы в ее КН-форме каждый дизъюнкт содержал слагаемым хотя бы одну
переменную вместе с ее отрицанием.
Теорема. Критерий тождественно ложной формулы алгебры логики:
Для того чтобы формула логики высказываний была тождественно ложной,
необходимо и достаточно, чтобы в ее ДН-форме каждый конъюнкт содержал
сомножителем хотя бы одну переменную вместе с ее отрицанием.
Упражнения
Задание 1.1. Докажите тождества аналитически и проверьте с помощью таблицы
истинности:
а) x  1  1 ;
г) x  x  1 ;
д) x  x  0
б) x | 0  1 ;
в) x  1  0 ;
е) 0  x  1
ж) x  x  1 ;
з) x | 1  x ;
и) x  x  x ;
к) x  0  x ;
Задание 1.2. Докажите или опровергните:
а) AB=1AB=1;
е) AB=1AB=1;
б) (AB)(BC)=AC
ж) AB=BA;
в) A(AB) =1;
з) A(BC)((AB)(AC))=1.
г) x  x  x ;
и); x | y  x  y
д) x  x  0 ;
к) x  y  x | y
Задание 1.3. Задана формула ( x  y )  x  z  ( x  y ) .
а) Выпишите все возможные подформулы этой формулы.
б) Постройте граф-схему этой формулы.
в) Минимизируйте формулу.

4

Решение: а) Подформулами будут все переменные x, y, z, входящие в данную
формулу (это подформулы с нулевым числом логических связок). Подформулы с одной
логической связкой: x , y , z . Подформулы с двумя логическими связками:

x  y, x  z , x  y .

Подформула
с
четырьмя
логическими связками: z  ( x  y ) . Пять логических
связок у подформулы x  z  ( x  y ) и т.д.
б) Граф-схема формулы ( x  y )  xz ( x  y ) имеет
вид (рис.1):
в)
Минимизируем
формулу,
используя
равносильности алгебры логики:
( x  y )  xz ( x  y ) =

f8
f2



f1



f7
f4



f6




x
( x  y )  xzy  x  y  xzy  ( x  y )  xzy 
f3 f5
= ( x  y )  ( x  y  z )  xy  xz  y  xz  y .

 y
x
y
Задание 1.4. Выпишите все возможные
f
подформулы заданных формул. Составив таблицы
x
истинности этих формул, докажите, что они являются
z
тавтологиями:
Рис.1 Граф-схема для
а) ((( X  Y )  Z )  ( X  (Y  Z )) (ассоциативность
задания 1.3
конъюнкции);
б) ((( X  Y )  Z )  ( X  (Y  Z )) (ассоциативность
дизъюнкции);
в) ( X  (Y  Z ))  (( X  Z )  ( X  Z )) (дистрибутивность конъюнкции относительно
дизъюнкции).
г) ( X  (Y  Z ))  (( X  Z )  ( X  Z )) (дистрибутивность дизъюнкции относительно
конъюнкции).
д) X  ( X  Y )  X (закон поглощения);
е) X  ( X  Y )  X (закон поглощения);
ж) X  ( X  Y )  X  Y (закон поглощения);
з) X  ( X  Y )  X  Y (закон поглощения);
и) ( X  Y )  ( X  Y )  X (закон склеивания);
к) ( X  Y )  ( X  Y )  X (закон склеивания).
Задание 1.5. Определите логическое значение последнего высказывания, исходя из
логических значений всех предыдущих высказываний:
а) ( A  B )  A  1, A  B  1, A  B  ?;
Решение: Из первого условия ( A  B )  A  1 заключаем, что невозможна ситуация,
когда ( A  B )  1 , а A = 0, т.е. A = 0 и при этом В = 1. Второе условие A  B  1 исключает
ситуацию, при которой A  1 и B  0. Следовательно, высказывания А и В имеют
одинаковые значения истинности. Значит, одинаковые значения истинности имеют и их
отрицания A и B. Отсюда высказывание A  B будет истинным.
б) A  B  1, ( A  B )( A  B )  ?
Решение: Из условия A  B  1 следует, что A и В имеют одинаковые значения
истинности. Тогда одинаковые значения истинности имеют и их отрицания A и B.
Значит, обе импликации A  B и A  B истинны. Следовательно, истинна и
конъюнкция двух последних высказываний.

5

Задание 1.6. Выполните задание по образцу задания 1.5.Определите логическое
значение последнего высказывания, исходя из логических значений всех предыдущих
высказываний:
а) A  B  1, A  B  0, B  A  ;
б) A  B --">