Крюкова А.Л. Методические указания к выполнению контрольной работы по матлогике 2017
.pdfФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ И НАУКЕ РОССИЙСКОЙ ФЕДЕРАЦИИ
ВОЛОГОДСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ
Методические указания к выполнению контрольной работы
по математической логике
ВОЛОГДА
2007
Рекомендуемая литература
1.Игошин В.И. Математическая логика и теория алгоритмов. – М.: Академия, 2004.
2.Тимофеева И.Л. Математическая логика. – М.: Прометей, 2003.
3.Лихтарников Л.М., Сукачева Т.Г. Математическая логика.– С-Пб.: Лань, 1999.
4.Мендельсон Э. Введение в математическую логику. – М: Наука, 1976.
5.Эдельман С.Л. Математическая логика. – М.: Высшая школа, 1975.
§1. Варианты контрольных заданий
I.Составить таблицу истинности для формул алгебры высказываний А, В и сделать вывод о их истинности, выполнимости или ложности. Восстановить, если это возможно, для каждой из формул СКНФ, СДНФ.
1.А= p & q p q r ,
2.А= p q & r q p r q ,
3.А= p q & p r p q & r ,
4.А= p q p r & q ,
5.А= p r q ~ p q & r ,
6.А= p q r p ,
7.А= p & q s & q p s ,
8.А= p q p r & q ,
9.А= p q s & q p s ,
10. А= q p q r p & q ,
II. Упростить формулы А и В, если это возможно:
В= p q r q r p ; В= p r q ~ p q & r & q ; В= r q r p q & p ;
В= p q s q p s ;
В= p q p r |
q & r ; |
В= p & q s & q |
s p s ; |
В= p q p r & q |
r ; |
В= p q p r p q & r ; В= p q & r q p r q ; В= r r p q & p .
11. А= z |
x & y , |
12.А= z x & y ,
13.А= z x y ,
14. |
А= z & x |
y , |
15. |
А= z x |
y , |
16.А= z x & y ,
17.А= z x y ,
18.А= z x x & y ,
19. |
А= z x x & y , |
20. |
А= z & x x y , |
В= x & y z x & y z & p t r t x y & z ; В= x & y x & y & p t z r x y ;
В= x & y & z x & y & z & p t r z x y z ; В= x y x y & p t r z x & y ;
В= x ~ y x ~ y & p t r z x & y y & x ;
В= z t x y & p &t x y t & z ;
В= z t x y r & p &t x r y t & z ; В= z t y r & p &t y r t & z ; В= z t x r & p &t x r t & z ;
В= z t x ~ r & p &t x ~ r t & z .
III.Получите для данной формулы КНФ, ДНФ и выясните, является ли формула общезначимой, ложной или выполнимой, используя критерий общезначимости и (или) критерий ложности:
21.p q r p q r ,
22.p q r p r p q ,
23.p q p q r r ,
24.p q q & r p & r ,
1
25.p & q p p & q r ,
26.q & r p q r p ,
27.p q p p q & p ,
28.p q p q r r ,
29.p & q r p q r ,
30.p q r & p r p q .
IV. Составить РКС для формулы и упростить её, если это возможно:
31.x & y z x y & z ,
32.x y & z x & y z & x & y & z ,
33.x & y z x y & z ,
34.z x & y & x y & z ,
35.x y z y x ,
36.x & y y x & y & x ,
37.x y & y z x z ,
38.x y & z & y x u ,
39.x y x & y z ,
40.x y & y z & x .
V.Определите значения истинности следующих формул:
x P x, a ,y P a, y ,x P x,b ,y P b, y ,
x, y P x, y ,
y x P x, y ,
y, x P x, y ,x, y P x, y ,
|
|
|
|
|
|
|
|
|
|
||
Если предикат P |
|
x, y |
|
задан на множестве M |
|
a,b |
таблицей |
||||
51. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
y |
P x, y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
a |
0 |
|
|
|
|
|
|
|
|
|
a |
b |
1 |
|
|
|
|
|
|
|
|
|
b |
a |
0 |
|
|
|
|
|
|
|
|
|
b |
b |
1 |
|
|
|
|
52. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
y |
P x, y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
a |
0 |
|
|
|
|
|
|
|
|
|
a |
b |
1 |
|
|
|
|
|
|
|
|
|
b |
a |
0 |
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
|
b |
b |
0 |
53. |
|
|
|
|
x |
y |
P x, y |
|
|
|
|
|
a |
a |
0 |
|
a |
b |
0 |
|
b |
a |
0 |
|
b |
b |
1 |
54. |
|
|
|
|
x |
y |
P x, y |
|
|
|
|
|
a |
a |
1 |
|
a |
b |
1 |
|
b |
a |
0 |
|
b |
b |
1 |
55. |
|
|
|
|
x |
y |
P x, y |
|
|
|
|
|
a |
a |
1 |
|
a |
b |
0 |
|
b |
a |
0 |
|
b |
b |
1 |
56. |
|
|
|
|
x |
y |
P x, y |
|
|
|
|
|
a |
a |
0 |
|
a |
b |
1 |
|
b |
a |
1 |
|
b |
b |
0 |
57. |
|
|
|
|
x |
y |
P x, y |
|
|
|
|
|
a |
a |
1 |
|
a |
b |
0 |
|
b |
a |
0 |
|
b |
b |
0 |
58. |
|
|
|
|
x |
y |
P x, y |
|
|
|
|
|
a |
a |
1 |
|
a |
b |
0 |
|
b |
a |
1 |
|
b |
b |
1 |
59. |
|
|
|
|
x |
y |
P x, y |
|
|
|
|
|
a |
a |
1 |
|
a |
b |
1 |
|
b |
a |
1 |
|
b |
b |
0 |
60. |
|
|
|
|
x |
y |
P x, y |
|
|
|
|
|
a |
a |
1 |
|
a |
b |
0 |
|
|
|
3 |
b |
a |
1 |
b |
b |
0 |
VI. Привести к предварённой нормальной форме следующие формулы:
81.x y P x, y & x y Q x, y ,
82.x y Q x, y z u P z,u ,
83.x R x x Q x, y ,
84.P x R x &Q x, y ,
85.x A x ~ y A y ,
66.x A x y B y ,
67.x y P x, y & x y Q x, y ,
68.x y P x, y x y Q x, y ,
69.x A x ~ y A x, y ,
90. P x R x & Q x, y .
VII. Построить машину Тьюринга с внешним алфавитом 0,1 , реализующую вычисление функции
fx x n , где n – номер Вашего варианта.
§2. Примеры решения задач контрольной работы
Алгебра высказываний
Основным неопределяемым понятием математической логики является понятие «высказывания». Под высказыванием обычно понимают всякое повествовательное предложение, о котором можно сказать является оно истинным или ложным. Пример истинного высказывания «в
високосном году 366 дней», ложного – «число 29 делится на 13». Очевидно, предложение «Да здравствуют наши спортсмены!» не является высказыванием. Обычно высказывания обозначают
прописными латинскими |
буквами |
|
с индексами |
или без p, q, r,..., p1, p2 , p3 ,... . Тот факт, |
что |
|||||
утверждение p истинно обозначают |
|
p |
|
1, ложно – |
|
p |
|
0 . |
|
|
|
|
|
|
|
||||||
На множестве всех |
высказываний определим операции. Отрицанием высказывания |
p |
||||||||
называется высказывание «не p », обозначаемое p , которое истинно, когда p ложно, и наоборот,
p ложно, когда p истинно. Будем иллюстрировать действие операций таблицами истинности. p p
01
10
Конъюнкцией двух высказываний p , q назовём новое высказывание « p и q », обозначаемое p & q , которое истинно в том и только в том случае, когда оба высказывания p , q истинны.
p |
q |
|
p & q |
|
|
|
|
0 |
0 |
|
0 |
0 |
1 |
|
0 |
1 |
0 |
|
0 |
1 |
1 |
|
1 |
|
|
4 |
|
Дизъюнкцией двух высказываний p , q называется новое высказывание « p или q », обозначаемое |
||||
p q , которое истинно, когда хотя бы одно из высказываний p , q истинно. |
||||
|
|
|
|
|
|
p |
q |
p q |
|
|
|
|
|
|
|
0 |
0 |
0 |
|
|
0 |
1 |
1 |
|
|
1 |
0 |
1 |
|
|
1 |
1 |
1 |
|
Импликацией двух |
высказываний |
p , q |
назовём новое высказывание «если |
p , то |
q », |
|||
обозначаемое p q , |
которое ложно только в том случае, когда высказывание p |
истинно, |
а q |
|||||
ложно. В этом случае p называют посылкой, q – заключением. |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
p |
q |
p q |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
1 |
|
|
|
|
|
|
0 |
1 |
1 |
|
|
|
|
|
|
1 |
0 |
0 |
|
|
|
|
|
|
1 |
1 |
1 |
|
|
|
Эквиваленцией двух высказываний |
p , q называется новое высказывание « p тогда и только тогда, |
|||||||
когда q », обозначаемое p q , которое истинно, когда p , q принимают одинаковые истинностные |
||||||||
значения.
p |
q |
p q |
|
|
|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
Под высказывательной переменной часто понимают переменные, которые могут принимать одно из возможных истинностных значений: истина или ложь. Из этих переменных с помощью символов , &, , , ~ и скобок будем строить осмысленные выражения – формулы. Такое
определение основано на интуитивных представлениях читателя о формулах. Строгое определение формулы языка высказываний смотри, например, в [2] пункт 1.2. Обычно порядок выполнения операций в формуле указывается скобками. Чтобы избежать большого количества скобок, договоримся о порядке выполнения логических операций: , &, , , ~ . Это значит, что при
отсутствии скобок сначала будем выполнять отрицание, затем конъюнкцию и т.д. Теперь можно перейти к разбору первого задания.
I.Составить таблицу истинности для формул алгебры высказываний А, В и сделать вывод о их истинности, выполнимости или ложности. Восстановить, если это возможно, для каждой из формул СКНФ, СДНФ.
Перед выполнением первого задания рекомендуем ознакомиться с §5 [1], §10, 11 [3].
А= x y x & y x y ;
Таблица 1
|
|
|
|
|
|
|
|
|
x |
y |
x y |
x |
y |
x & y |
x & y x |
x & y x y |
A |
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
Правило отыскания совершенной дизъюнктивной нормальной формы для данной формулы:
Выберем в таблице истинности те строки, в которых формула принимает истинное значение.
Для каждой из выбранных строк составим выражение, называемое полной элементарной конъюнкцией. В строке таблицы истинности напротив каждой переменной указано значение 0 или 1. Составляем конъюнкцию из всех переменных, от которых зависит наша формула, по следующему принципу: если в строке напротив переменной расположена 1, то в конъюнкцию внесём саму переменную, если – 0, то её отрицание.
5
Все составленные полные элементарные конъюнкции соединяем знаком операции дизъюнкции.
Составим СДНФ для формулы А. В таблице 1 три строки, в последней ячейке которых содержится 1, – первая, третья и четвёртая. С начала составим полную элементарную конъюнкцию (п.э.к.) для первой строки. Так как в первой строке напротив переменной x находится 0, то в п.э.к. войдёт выражение x , тоже можно сказать и о переменной y. Таким образом, п.э.к. для первой строки имеет вид x & y . В третьей строке таблицы 1 напротив переменной x расположена 1, а напротив
переменной y – 0, тогда, п.э.к. для третьей строки имеет вид x & y . Наконец, п.э.к. для четвёртой строки имеет вид x & y . Соединив, полученные полные элементарные конъюнкции, между собой знаками дизъюнкции, получим СДНФ A x & y x & y x & y .
Правило отыскания совершенной конъюнктивной нормальной формы для данной формулы:
Выберем в таблице истинности те строки, в которых формула принимает ложное значение.
Для каждой из выбранных строк составим выражение, называемое полной элементарной дизъюнкцией. В строке таблицы истинности напротив каждой переменной указано значение 0 или 1. Составляем дизъюнкцию из всех переменных, от которых зависит наша формула, по следующему принципу: если в строке напротив переменной расположена 1, то в конъюнкцию внесём отрицание переменной, если – 0, то саму переменную.
Все составленные полные элементарные конъюнкции соединяем знаком операции конъюнкции.
Так как таблица 1 содержит только одну строку, в последней ячейке которой находится 0, то будет состоять из одной полной элементарной дизъюнкции. Во второй строке напротив переменной x находится 0, напротив переменной y – 1, тогда полная элементарная дизъюнкция имеет вид x y ,
и СКНФ A x y.
Замечание.
В таблице истинности может вообще не оказаться строк, в последней ячейке которых находится нуль (единица), тогда СКНФ (СДНФ) для такой формулы вообще составить невозможно.
Выполним аналогичные построения для формулы В= x & y y x z .
Таблица 2
|
|
|
|
|
|
|
|
|
|
x |
y |
z |
x |
y |
z |
x & y |
y x |
y x z |
B |
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
СДНФ B x & y & z x & y & z x & y & z x & y & z x & y & z
x & y & z x & y & z x & y & z
СКНФ B не существует.
Формула называется общезначимой (тождественно истинной), если она примет значение 1 на всех наборах значений входящих в нее переменных. Формула называется ложной, если она примет значение 0 на всех наборах значений входящих в нее переменных. Остальные формулы будем называть выполнимыми.
Для того чтобы выяснить является ли формула общезначимой, ложной или выполнимой достаточно построить таблицу истинности этой формулы.
6
С= x y x & y ;
Таблица 3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
y |
|
x y |
x y |
x & y |
x & y |
x y x & y |
С |
|||
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
|
|||||
|
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
|
|||||
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
|
|||||
|
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
|
|||||
Формула С является ложной. |
|
|
|
|
|
|
|
|
||||||
D= p & q ~ q ~ q p ; |
|
|
|
|
|
|
|
|
||||||
Таблица 4 |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
p |
|
q |
|
p & q |
|
p & q ~ q |
q p |
|
p & q ~ q ~ q p |
|
||
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
1 |
|
1 |
|
|
1 |
1 |
|
1 |
|
|
|
|
|
1 |
|
0 |
|
0 |
|
|
1 |
1 |
|
1 |
|
|
|
|
0 |
|
1 |
|
0 |
|
|
0 |
0 |
|
1 |
|
|
|
|
0 |
|
0 |
|
0 |
|
|
1 |
1 |
|
1 |
|
|
Формула D является общезначимой.
Вернёмся теперь к таблицам 1 и 2. Так как в последнем столбце таблицы 1 находятся и нуль, и единицы, то формула А – выполнима. Из таблицы 2 видно, что формула В – общезначима.
Две формулы алгебры высказываний называются равносильными, если на одинаковых наборах значений, входящих в них переменных, они принимают одинаковые истинностные значения. Тот факт, что формула F равносильна формуле E, будем обозначать следующим образом F E. Замена формулы (или её части) на равносильную может приводить в существенному упрощению записи, но при этом истинностное значение не меняется. Будем считать, что формула упрощена, если она содержит меньшее либо равное число переменных, по отношению к первоначальной, и число операций в формуле меньше, чем в первоначальной. Без дополнительного доказательства будем использовать следующие основные равносильности:
Коммутативные законы
1.1. A& B B & A 1.2. A B B A
Ассоциативные законы
2.1. A& B &C A & B &C |
2.2. A B C A B C |
Дистрибутивные законы |
|
3.1. A& B C A& B A&C |
3.2. A B &C A B & A C |
Законы поглощения |
|
4.1. A& A B A |
4.2. A A & B A |
Законы де Моргана |
|
5.1. A & B A B |
5.2. A B A & B |
Законы идемпотентности |
|
6.1. A& A A |
6.2. A A A |
7.1. A&1 A |
7.2. A 1 1 |
8.1. A&0 0 |
8.2. A 0 A |
Закон противоречия |
Закон исключённого третьего |
9.1. A& A 0 |
9.2. A A 1 |
Закон двойного отрицания
10.A A
11.p q p q
12.p ~ q p q & q p
Теперь мы можем перейти к разбору второго задания.
7
II.Упростить формулы А и В, если это возможно.
А= x ~ y & x y
Решение: |
Комментарий |
x ~ y & x y |
Исключим из нашей формулы операцию эквиваленция, для |
|
этого воспользуемся равносильностью 12. |
x y & y x & x y |
заменим операцию импликации согласно равносильности 11. |
x y & y x & x y |
вынесем из второй и третьей скобки общий множитель, такое |
|
преобразование возможно, так как выполнен дистрибутивный |
|
закон 3.2. |
x y & x y & y |
теперь воспользуемся равносильностью 9.1. |
x y & x 0 |
применим 8.2. |
x y & x |
согласно коммутативному закону 1.1 |
x & x y |
используем дистрибутивный закон 3.1. для перемножения |
|
скобок |
x & x y & x |
опять воспользуемся 9.1. |
0 x & y |
снова применим 8.2. |
x & y |
упрощение завершено. |
В = x & z x & z y & z x & y & z
Решение:
x & z x & z y & z x & y & z
x & z x & z y & z y & z & x
x & z x & z y & z
x & z z y & z
x &1 y & z
x y & z
Комментарий Для того чтобы «увидеть» закон поглощения
заключим в скобки последние два члена дизъюнкции. Кроме того, воспользуемся коммутативностью операции конъюнкция 1.1.
применим закон поглощения 4.2. В данном случае
A y & z , B x
из первой и второй скобок вынесем общий множитель применим закон исключенного третьего
согласно 7.1. можно записать упрощение завершено.
III.Получите для данной формулы КНФ, ДНФ и выясните, является ли формула F общезначимой, ложной или выполнимой, используя критерий общезначимости и (или) ложности.
Перед выполнением третьего задания рекомендуем ознакомиться с §10, 11 [3].
F= p q r & p r p q
Решение: |
Комментарий |
p q r & p r p q |
Заменим операции импликации в скобках |
|
согласно равносильности 11. |
p q r & p r p q |
теперь таким же образом преобразуем внешнюю |
|
импликацию |
p q r & p r p q |
применим закон двойного отрицания 10. |
p q r & p r p q |
внесём отрицание в первую скобку, используя |
|
|
|
закон де Моргана 5.2. |
p q r p r p q |
ещё раз воспользуемся тем же законом для того, |
|
чтобы внести отрицания в скобки. |
p & q r p & r p q |
воспользуемся дистрибутивным законом 3.1. |
|
8 |
p & q p & r p & r p q |
формула приведена к дизъюнктивно |
|
нормальной форме. |
ДНФ F p & q p & r p & r p q .
Решение:
p q r & p r p q
p q r & p r p q
p q r & p r p q
p q r & p r p q
p q r p r p q
p & q r p & r p q
p & q r p p & r q
p & q r p q
p & q r p q
p p q & q r p q
p q & p q r
КНФ F p q & p q r .
Критерий общезначимости:
Комментарий Заменим операции импликации согласно равносильности 11.
теперь таким же образом преобразуем внешнюю импликацию применим закон двойного отрицания 10.
внесём отрицание в первую скобку, используя закон де Моргана 5.2.
ещё раз воспользуемся тем же законом для того, чтобы внести отрицания в скобки воспользуемся коммутативным законом 1.2.
теперь применим закон поглощения
заключим в скобки два последних члена дизъюнкции воспользуемся дистрибутивным законом 3.1.
произведем упрощение в каждой из полученных скобок, используя закон идемпотентности 6.2. формула приведена к конъюнктивно нормальной форме.
Формула общезначима тогда и только тогда, когда каждая элементарная дизъюнкция равносильной ей КНФ содержит, по крайней мере, одну высказывательную переменную вместе с её отрицанием.
Критерий ложности:
Формула ложна тогда и только тогда, когда каждая элементарная конъюнкция равносильной ей ДНФ содержит, по крайней мере, одну высказывательную переменную вместе с её отрицанием.
Формула, не удовлетворяющая ни критерию ложности, ни критерию общезначимости является выполнимой.
Формула F= p q r & p r p q – выполнима.
IV. Составить РКС для формулы a & b a & a & d c & b & e a & d & e и
упростить её, если это возможно.
Перед выполнением четвёртого задания рекомендуем ознакомиться с §12 [1]. Решение:
Для составления схемы нужно помнить, что операция конъюнкции изображается на схеме последовательным соединением, а дизъюнкции – параллельным.
9