Similar presentations:
Алгебра высказываний при решении логических задач. Дизъюнктивные нормальные формы Лекция 3
1. Алгебра высказываний Лекция 3
Цель: ознакомить с понятиями ДНФ, СДНФ, сформироватьнавыки приведения высказываний к ДНФ и СДНФ,
показать возможности применения алгебры высказываний при
решении логических задач, упрощении переключательных схем
2. Дизъюнктивные нормальные формы (ДНФ)
Определение 1F,если a = 1
F
F ,если a = 0.
a
Утверждение 2
A 1 A
Доказательство
A
0
0
1
1
a
0
1
0
1
Aa
1
0
0
1
3.
Определение 3Конъюнкция логических переменных
элементарной конъюнкцией (ЭК).
Общий вид элементарной конъюнкции:
или
их
отрицаний
называется
A1a1 A2a2 ... Anan
Пример
AC, AB, A C , B C, A BC, B C , A
Определение 4
Высказывание называется дизъюнктивной нормальной формой (ДНФ), если оно
представляет собою дизъюнкцию элементарных конъюнкций.
Общий вид ДНФ: K1 K2 ... Km
4.
ПримерыAB C
A B C
A
A B
A C
A C
ABC BC A
5.
ТеоремаЛюбое высказывание приводимо к ДНФ.
Схема приведения высказывания к ДНФ
1) Избавиться от импликации и эквивалентности, используя законы
16), 17)
2) Донести отрицания до переменных, используя законы Моргана.
3) Раскрыть скобки, используя дистрибутивные законы.
4) Упростить полученное высказывание.
6. Пример
Привести высказывание к ДНФF AC B A C B
AC B A C B
AC B A C B AC B A C B
A C B(C B) ACB A(C B)
A C B A C B ACB AC B
A C BC C B B ABC C ABCB
A C B BC
A C
A C B ABC
A C ( B B)
7. Построение высказываний по таблице истинности. Совершенные дизъюнктивные нормальные формы (СДНФ)
Определение 1Пусть X A1 , A2 ,..., An – некоторое множество логических
переменных. Элементарная конъюнкция, в которую входят все
логические переменные, называется полной элементарной
конъюнкцией относительно множества X .
X A, B, C
Пример
A, AC , ABC , B AC, B AC , ABC
8.
СДНФОпределение 2
• Дизъюнктивная нормальная форма называется совершенной
(СДНФ), если все составляющие ее элементарные
конъюнкции являются полными.
X A, B, C
Примеры
AB BCA B
ABC
ABC ABC AB
ABC ABC ABC
ABC ABC ABC
9. Приведение высказывания к СДНФ
ТеоремаВысказывание, не являющееся тождественно ложным, приводимо к
СДНФ.
Правило приведения высказывания к СДНФ
• СДНФ содержит столько полных элементарных конъюнкций, сколько
единиц в последнем столбце таблице истинности.
• Вид каждой полной элементарной конъюнкции определяется
соответствующим набором значений переменных, а именно, если
переменная принимает значение 0, то над ней в полной элементарной
конъюнкцией ставится отрицание, иначе – отрицание не ставится.
10. Пример
• Построить по таблице истинности СДНФF
A
B
C
0
0
0
1
0
0
1
0
0
1
0
1
0
1
1
0
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
1
F ABC ABC ABC ABC
11. Задача
• «Вернувшись домой, Мегрэ позвонил на набережную Орфевр.• - Говорит Мегрэ. Есть новости?
• - Да, шеф. Поступили сообщения от инспекторов.
• Торранс установил, что если Франсуа был пьян, то либо Этьен
убийца, либо Франсуа лжет.
• Жуссье считает, что или Этьен убийца, или Франсуа не был пьян
и убийство произошло после полуночи.
• Инспектор Люка просил передать Вам, что если убийство
произошло после полуночи, то либо Этьен убийца, либо Франсуа
лжет.
• Затем звонила …
• - Все. Спасибо. Этого достаточно. – Комиссар положил трубку.
Он знал, что трезвый Франсуа никогда не лжет. Теперь он знал
все.»
• Что знал Мегрэ?
12. Решение задачи
Пусть
P=« Франсуа был пьян»
L=«Франсуа лжет»
I=«Этьен убийца»
U=«Убийство произошло после полуночи»
Тогда получим высказывание
P I L (I PU )(U I L) 1
P I L (I PU )(U I L)
I ( P L) PU (U L)
I PUL
•Так как
PUL 0 , то Этьен - убийца
13. Приложения алгебры высказываний. Исследование переключательных схем
Переключательная схема — это схематическое изображениенекоторого устройства, состоящего из переключателей и
соединяющих их проводников, а также из входов и
выходов, на которые подаётся и с которых снимается
электрический сигнал.
Каждый переключатель X имеет только два состояния:
замкнутое (X=1) и разомкнутое(X=0). .
14. Переключательные схемы
AA
F=A
B
F=AB
A
B
F A B
15. Переключательные схемы Пример 1
BC
A
A
C
A
B
A
C
B
A
A
C
A
B
C
A
B
C
B
A
C
B
C
A
B
B
A B C B B A B AC BC .
B
F A BC AC C A AB B ABC AB A C
16. Переключательные схемы. Пример 1
F AС BC AC A AB B ABC AB A CA B C B B A B AC BC
AС A B AB A C
A B BС B A AC BC
ABC AB A B B A AC BC
B( AC A) B AC BC
B(C A) BAC BC AB BAC
B C A AC B C A C B
B
17. Переключательные схемы. Пример 2
AA
C
B
M
B
B
C
C
C
B
B
A
A
A
A
B
C
B
B
C
B
C
B
A
A
B
B
A
C
C
A
N
18. Переключательные схемы. Пример 2
A0
B
0
C
0
F
0
0
0
1
0
0
0
1
1
0
1
1
1
1
1
1
0
0
1
0
1
0
0
0
0
1
1
1
0
F ABC ABC AB C C AB
A
B
19. Задача на голосование
Построить контактную схему для оценкирезультатов спортивного соревнования тремя
судьями при условиях: судья засчитавший
результат, нажимает имеющуюся в его
распоряжении кнопку, а судья, не
засчитывающий результат, кнопки не
нажимает. В случае, если кнопки нажали не
менее двух судей, загорается лампочка
(положительное решение судей принятое
большинством голосов).
20. Задача на голосование
• РешениеA
0
0
B
0
0
C
0
1
F
0
0
0
0
1
1
1
0
0
1
0
0
1
0
1
0
1
1
1
1
1
1
0
1
1
1
F ABC ABC ABC ABC
ABC ABC AB ABC AC AB
BC AC AB BC A( B C )
B
C
B
A
C
21. Задачи
2. Голосуют три человека A, B, C. Предложениепринимается большинством голосов, причём C
- председатель, обладающий правом вето, т. е.
если он голосует "против", то предложение не
принимается
22. Задачи
Задачи
3. Голосуют три человека A, B, C. Предложение принимается
большинством голосов, причём выполняются следующие условия:
а) если C голосует "за", то B голосует "против";
б) C голосует "против" тогда и только тогда, когда B голосует "за";
в) если C голосует "за" или B голосует "за", то A голосует "против";
г) A и B- коалиция, т. е. голосуют одинаково, а C им противоречит;
д) C подозревает A и B в коалиции, т. е. если A и B голосуют
одинаково, то C им противоречит;
е) если C голосует "за", то A голосует "за" тогда и только тогда, когда
B голосует "против";
ж) если B голосует "за", то C голосует "против" тогда и только тогда,
когда A голосует "против";
з) если A голосует "за" или B голосует "против", то C голосует "за".