Решение логических задач

1. Решение логических задач

2.

Задача. Методом резолюций проверьте
справедливость следующих рассуждений.
Допустим, что если руководство вуза
действует по закону высшей школы, то
студент-задолжник не отчисляется, если он
является задолжником не более одного
месяца
или
преподаватель-экзаменатор
уходит в отпуск. Не будет ли отчислен
студент-задолжник, если руководство вуза
действует по закону высшей школы и сессия
только что закончилась?

3.

Решение.
Введем
обозначения
для
следующих высказываний:
D = «руководство вуза действует по закону
высшей школы»;
S = «студент-задолжник отчисляется»;
P = «преподаватель-экзаменатор уходит в
отпуск»;
T = «студент является задолжником не более
одного месяца».
Первое утверждение задачи

4.

Сформулированное в вопросе задачи
утверждение
выражается
следующим
сложным высказыванием:
По условию задачи требуется определить,
выполняется ли логическое следование

5.

Рассмотрим множество дизъюнктов полученной
КНФ формулы
и построим резолютивный вывод значения 0 из
этого множества S.

6. Алгебра логических значений

7.

Определение. Алгеброй называется непустое
множество A с фиксированным набором операций
f1,f2,…,fk,
имеющих
соответствующие
определенные
арности n1,n2,…,nk. При этом
множество A называется базисным множеством
алгебры и набор символов операций ={f1,f2,…,fk}
соответствующей арности n1,n2,…,nk называется
алгебраическим типом (или сигнатурой) алгебры.
Такая
алгебра
сокращенно
обозначается
(A;f1,f2,…,fk ), или (A; ), или просто буквой A и
называется алгеброй типа , или сокращенно алгеброй.

8.

Пример алгебры дает множество {0,1}
истинностных значений высказываний с nарными операциями F , которые являются
функциями истинностных значений формул
X 1 ,..., X n ,
логики
высказываний
образованных с помощью n пропозициональных
переменных X 1 ,..., X n .
X
Формула
определяет
унарную
операцию F F X (x) , которая обозначается
символом x и называется отрицанием или
дополнением переменной x .

9.

Формулы X Y , X Y определяют
бинарные операции F FX Y ( x, y ) , F FX Y ( x, y) ,
которые обозначаются соответственно символами
x y,x y
и называются дизъюнкцией и
конъюнкцией переменных x ,y.
Операция x y иногда называется также
объединением или суммой переменных x ,y и
обозначается соответственно через x y или
x y.
Операция x y иногда называется также
пересечением или произведением переменных x ,y
и обозначается соответственно через x y или
x y.

10.

Алгебра B=({0,1}, , , ) впервые была введена
в 19-ом веке английским математиком Дж.Булем с
целью применения в логике математических
методов.
Поэтому эта алгебра называется алгеброй Буля
или алгеброй логических значений.

11.

Теорема.
Алгебра
Буля
B=({0,1}, , , )
удовлетворяет свойствам:
1) a (b c) (a b) c , a (b c) (a b) c –
ассоциативность дизъюнкции и конъюнкции;
2) a b b a , a b b a – коммутативность
дизъюнкции и конъюнкции;
a a a
3) a a a ,
–
идемпотентность
дизъюнкции и конъюнкции;
4) a (b c) (a b) (a c) , a (b c) (a b) (a c)
– дистрибутивность соответственно конъюнкции
относительно
дизъюнкции
и
дизъюнкции
относительно конъюнкции;

12.

5) (a ) a – идемпотентность дополнения;
6) (a b) a b , (a b) a b – законы де
Моргана;
a (a b) a
7) a (a b) a ,
–
законы
поглощения;
8) a a 1 , a a 0
– характеристическое
свойство дополнения,
a 1 a
9) a 1 1,
– характеристическое
свойство наибольшего элемента 1,
10) a 0 a , a 0 0 – характеристическое
свойство наименьшего элемента 0.

13. Булевы многочлены и булевы функции

14.

Для описания алгебраических свойств булевых
алгебр
используются
формулы,
которые
называются булевыми многочленами и которые
образованы
из
булевых
переменных
x,y,…(принимающих значения 0,1) и символов
булевых операций +, , по следующим правилам:
1)
все булевы переменные x,y,… и символы 0,1
– булевы многочлены;
2)
если p и q – булевы многочлены, то
таковыми являются выражения
p q , p q , p .

15.

Если p образован с помощью x1 ,..., xn , то он
обозначается p( x1,..., xn ) .
Множество всех булевых многочленов от n
переменных обозначим Pn .
Если в p( x1 ,..., xn ) вместо переменных x1 ,..., xn
подставить произвольные значения a1 ,..., an из
множества B, то в результате вычислений
получится некоторый элемент p(a1,..., an ) алгебры B.
Каждый булев многочлен p( x1,..., xn ) определяет
отображение p : Bn B , которое называется булевой
полиномиальной функцией, определяемой булевым
многочленом p( x1 ,..., xn ) .

16.

p, q Pn
Определение. Булевы многочлены
называются
эквивалентными,
если
они
определяют одну и ту же булеву полиномиальную
функцию, т.е. p q .
Символическая запись: p ~ q или просто p q .
Бинарное
отношение
~
является
эквивалентностью на множестве Pn .
Классы эквивалентности p {q Pn : p ~ q} ,
образуют фактор-множество Pn / ~ { p : p Pn } .
Полные системы представителей этого фактормножества называются системами нормальных
форм булевых многочленов.

17.

Для булевой переменной x и {0,1} положим:
x, если 1,
x
x , если 0.
x
называется литерой.
Выражение
Литера или конъюнкция (соответственно,
дизъюнкция) литер называется конъюнктом
(соответственно, дизъюнктом).
Конъюнкт (дизъюнкт) называется совершенным,
если он содержит все булевы переменные
рассматриваемой формулы.

18.

Дизъюнкт или конъюнкция (совершенных)
дизъюнктов
называется
(совершенной)
конъюнктивной нормальной формой. Сокращенно
КНФ и СКНФ, соответственно.
Конъюнкт или дизъюнкция (совершенных)
конъюнктов
называется
(совершенной)
дизъюнктивной нормальной формой. Сокращенно
ДНФ и СДНФ, соответственно.

19.

Теорема. Любая булева функция f:Bn B
является булевой полиномиальной функцией
следующих булевых многочленов:
pf
f 1,..., n x1
1
1 ,..., n B n
n
...xn
и
qf
( f n 1,..., n x1
1
1 ,..., n B
n
... xn )
.

20.

Следствие 1. Если булева функция f:Bn B не
равна тождественно нулю, то она является
булевой полиномиальной функцией следующей
совершенной дизъюнктивной нормальной формы
pf
1
n
x1 ...xn
1 ,..., n B n ,
f 1 ,..., n 1
,
которая называется совершенной дизъюнктивной
нормальной формой (сокращенно СДНФ)
функции f .

21.

Следствие 2. Если булева функция f:Bn B не
равна тождественно единице, то она является
булевой полиномиальной функцией следующей
совершенной конъюнктивной нормальной формы
qf
1
( x1 ... x n n )
1 ,..., n B n ,
f 1 ,..., n 0
,
которая называется совершенной конъюнктивной
нормальной
формой
(сокращенно
СКНФ)
функции f .

22.

Алгоритм нахождения СДНФ и СКНФ функции
f:Bn B:
1. Составить таблицу значений функции f и
добавить к ней два дополнительных столбца с
заголовками «Совершенные конъюнкты» и
«Совершенные дизъюнкты».
2. Если при значениях x1 k1,..., xn kn значение
функции f равно 1, то в соответствующей строке
таблицы в столбце «Совершенные конъюнкты»
k1
x1 ...xnk n
записать
конъюнкт
и в столбце
«Совершенные дизъюнкты» сделать прочерк (при
1
0
x
x
x
x ).
этом
и

23.

3. Если при значениях x1 m1,..., xn mn значение
функции f равно 0, то в соответствующей строке таблицы
в столбце «Совершенные дизъюнкты» записать
дизъюнкт x1m1 ... xnmn и в столбце «Совершенные
конъюнкты» сделать прочерк.
x1
…
xn
...
f x1 ,..., xn
…
…
…
…
…
…
…
...
...
...
...
...
…
1
…
0
…
k1
…
m1
…
kn
…
mn
…
Совершенные Совершенные
конъюнкты
дизъюнкты
…
…
–
x1k1 ...xnk n
…
–
…
x1m1 ... xnmn
…
…

24.

4. Дизъюнкция полученных совершенных
конъюнктов
k1
kn
x1 ...xn
+…
является СДНФ функции f , конъюнкция
полученных совершенных дизъюнктов
( x1m1 ... xnmn ) ...
является СКНФ функции f .

25. Системы булевых функций

26.

Операция отрицания является одной из
четырех булевых функций от одной переменной,
которые перечисляются в следующей таблице:
x
f1 ( x)
f 2 ( x)
f 3 ( x)
f 4 ( x)
0 0
0
1
1
1 0
1
0
1

27.

Операции дизъюнкция + и конъюнкция являются
примерами двух из шестнадцати булевых функций от
двух переменных, которые перечисляются в следующей
таблице:
x y
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10
f11
f12
f13
f14
f15
f16
0 0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0 1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1 0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1 1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
x
y
+
y
x
1
Функция f15 ( x, y ) f 2 ( x, y )
обозначается x | y .
f 9 ( x, y ) f8 ( x, y )
Функция
обозначается x y .
штрих
-
Шеффера,
стрелка
Пирса,

28.

Определение. Суперпозицией булевых функций
g ( y1 ,..., ym ) и h1 ( x1 ,..., xn ) , …, hm ( x1 ,..., xn ) называется
булева функция f ( x1,..., xn ) , значения которой
определяются по формуле:
f ( x1 ,..., xn ) g h1 ( x1 ,..., xn ),..., hm ( x1 ,..., xn ) .
Для упрощения записи суперпозиции булевых
функций скобки по возможности опускаются с
учетом следующего приоритета выполнения
булевых операций: , и затем все остальные
операции.

29.

Лемма. Булевы функции от двух переменных
взаимосвязаны следующими свойствами:
1) ( x y ) x y , ( xy ) x y – законы де Моргана;
2) x xy x , x( x y) x – законы поглощения;
3) x x 1 , xx 0
– характеристическое
свойство отрицания;
4) x 1 1, x 1 x – характеристическое свойство
элемента 1;
x 0 0 – характеристическое
5) x 0 x ,
свойство элемента 0;
xy ( x y )
6) x y ( x y ) ,
– взаимосвязь
конъюнкции и дизъюнкции;
x y ( xy )
7) x y x y ,
– взаимосвязь
импликации с дизъюнкцией, конъюнкцией и
отрицанием;

30.

8) x y ( x y)( y x) , x y ( x y )( x y ) ;
xy ( x | y ) ( x | y ) | ( x | y ) ,
x x | x ,
9) x | y ( xy ) ,
x y x | y ( x | x) | ( y | y ) – взаимосвязь штриха
Шеффера
с
дизъюнкцией,
конъюнкцией
и
отрицанием;
10) x y ( x y) , x x x , x y ( x y) ( x y) ( x y) ,
xy x y ( x x) ( y y) – взаимосвязь стрелки
Пирса с дизъюнкцией, конъюнкцией и отрицанием;
11) x y y x , ( x y) z x ( y z) , x( y z) xy xz,
x 1 x ,
x x 0,
x 0 x,
x x 1
–
характеристическое свойство суммы Жегалкина;
x y x y 1,
x y xy x 1 ,
12) x y xy x y ,
x y ( x 1)( y 1) 1 x y xy
–
взаимосвязь
суммы Жегалкина с дизъюнкцией, конъюнкцией,
отрицанием, импликацией и эквивалентностью.