lec06
.pdf
Теорема 6.2.
Если функция g двойственна к функции , функция h двойственна к функции g: g = f *; h = g*, то
h ≡
(h = g* = (f *)* = f ).
Доказательство.
(f *)* = ( *(x1, x2, … xn))* ( ( 1, 2, … ))* = ( 1, 2, … ) = = (x1, x2, … xn) =
Следствие 6.1. (из теоремы 6.1 и 6.2): Если (x1, … xn) выражена через основные функции , &,¬, то для получения f (x1, … xn) достаточно заменить каждую из основных функций на двойственную: на &, & на (для остальных элементарных функций справедливо: на |, | на , на , на
, → на ← , ← на → ).
11
Пример 6.4. Нахождение * для элементарной функции эквивалентными преобразованиями.
Согласно следствия 6.1 для *:
1 2 = 1 2 1 2 =* = ( 1 2) & ( 1 2) = 1 2 1 2 = 1 2.
Пример 6.5.
Нахождение двойственной F* для формулы F:
F = ↓ ( ( )) →
F* = |( ( )) ←
12
Часть 2. Двойственность и СНФ.
Теорема о единственности СКНФ.
Теорема 6.3.
Если (x1, … xn) не тождественна 1, то она представима в виде СКНФ единственным образом.
Доказательство: из двойственности.
Рассмотрим *(x1, … xn) - двойственную функцию к (x1, … xn). Для * найдем СДНФ:
СДНФ * = D = K K … K |
|
|||||||
|
|
|
1 |
|
2 |
|
S |
|
Согласно теоремы 6.2 и следствия 6.1: |
|
|
|
|
||||
= ( *)* = D* = (K K … K |
) |
= |
||||||
|
|
1 |
|
2 |
|
S |
|
|
= … = D |
1 |
D |
2 |
… D |
S |
СКНФ . |
||
1 2 |
|
|
|
|
|
|||
14
Пример 6.6.
Найти по теореме 6.3 СНФ для функции (из примера 3.1)
(x1, x2, x3) = (00010111)
|
|
|
|
|
x1 |
x2 |
x3 |
(x1, x2, x3) |
конъюнкты дизъюнкты |
0 |
0 |
0 |
0 |
x1 x2 x3 |
|
|
|
|
|
0 |
0 |
1 |
0 |
x1 x2 ¬x3 |
|
|
|
|
|
0 |
1 |
0 |
0 |
x1 ¬x2 x3 |
|
|
|
|
|
0 |
1 |
1 |
1 |
¬x1 x2 x3 |
|
|
|
|
|
1 |
0 |
0 |
0 |
¬x1 x2 x3 |
|
|
|
|
|
1 |
0 |
1 |
1 |
x1 ¬x2 x3 |
|
|
|
|
|
1 |
1 |
0 |
1 |
x1 x2 ¬x3 |
|
|
|
|
|
1 |
1 |
1 |
1 |
x1 x2 x3 |
|
|
|
|
СДНФ = K1 K2 K3 K4; СКНФ = D1 D2 D3 D4
15
|
|
|
|
x1 |
x2 |
x3 |
* |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
конъюнкты
x1 x2 x3 x1 x2 ¬x3 x1 ¬x2 x3
x1 ¬x2 ¬x3
дизъюнкты
¬x1 x2 x3
x1 ¬x2 x3 x1 x2 ¬x3 x1 x2 x3
СДНФ = D = (¬x1 x2 x3) (x1 ¬x2 x3) (x1 x2 ¬x3) (x1 x2 x3) СКНФ * = K = (¬x1 x2 x3) (x1 ¬x2 x3) (x1 x2 ¬x3) (x1 x2 x3)
СКНФ = K = (x1 x2 x3) (x1 x2 ¬x3) (x1 ¬x2 x3) (¬x1 x2 x3) СДНФ * = D = (x1 x2 x3) (x1 x2 ¬x3) (x1 ¬x2 x3) (¬x1 x2 x3)
Можно сделать выводы: |
Подтверждаем, что |
|
1) СДНФ * = СКНФ |
3) |
(СКНФ *)* = СКНФ |
2) СКНФ * = СДНФ |
4) |
(СДНФ *)* = СДНФ |
Пример 6.7. Для формулы A = x(yz xy) (из примера 3.6) была получена СДНФ. Получим СКНФ используя вывод (1).
СДНФ А =
СДНФ A =
СДНФ A = =
= x y z x y (x z) (x )
СКНФ А = x y z x y (x z) (x )
17
Часть 3.
Приложения алгебры логики.
Релейно-контактные схемы.
РКС широко используются в ТАУ. Состав РКС:
1)переключатели - механические устройства, электромагнитные реле, полупроводники и т.д.;
2)соединяющие их проводники;
3)входы в схему и выходы из нее (клеммы, на которые подается электрическое напряжение) - полюса.
Простейшая схема: один переключатель Р, один вход А и один выход В (схема 1). Р поставим в соответствии высказывание р: “Переключатель Р замкнут”. Если р истинно, то схема пропускает ток. Если р ложно, то переключатель разомкнут и схема тока не проводит принимая во внимание не смысл высказывания, а только его значение, то любому высказыванию может быть поставлена в соответствие переключательная схема с двумя полюсами.
Формулам, включающим основные логические операции, также могут быть поставлены в соответствие переключательные схемы.
19
Конъюнкция двух высказываний P Q приведена на схеме 2:
а дизъюнкция P Q – на схеме 3:
20