Лекция №6. Тема: основные законы алгебры логики.

ü Идемпотентность дизъюнкции и конъюнкции X X↔X, X X↔X

 

ü Коммутативность X Y↔Y X, X Y↔Y X

 

 

ü Ассоциативность X Y Z - (X Y) Z↔X (Y Z)

X Y Z - (X Y) Z↔X (Y Z)

 

ü Дистрибутивность основных операций X (Y Z)=(X Y) (X Z)

X (Y Z)=(X U) (X Z)

‗

ü Двойное отрицание X↔X

_ _ ___

ü Закон Де Моргана X Y ↔ X Y

_ _ ____

X Y ↔ X Y

_

ü Склеивание (X Y) (X Y) = X

_

(X Y) (X Y) = X

 

ü Поглощение X (X Y) ↔ X

X (X Y) ↔ X

_

ü Исключение X X ↔ 1

 

ü Отрицание противоречия

 

ü Операции с логическими константами X 0 = X, X 0 = 0,

X 1 = 1, X 1 = X, X X = 0

 

Примеры:

X	Y	(X Y)	(X Y) X

 

1. F = (X Y) X =?

 

X	Y	X Y	X Y → X

2. F = X Y → X =?

 

 

_ _

A	B	C	_ A	_ B	_ B C	_ A B C	_ A B C A

3. F = A B С A =?

 

 

_

4. F = A (A B) (B → C) =?

A	B	C	_ B	A B	_ B → C	_ (A B) (B → C)	_ A (A B) (B → C)

 

_

5. F = X (Y ↓ Z) (X → Z) =?

 

X	Y	Z	_ Z	Y ↓ Z	_ X → Z	X (Y ↓ Z)	_ X (Y ↓ Z) (X → Z)

 

_

6.F = X → (Y ↔ Z) │ X =?

X	Y	Z	_ X	Y ↔ Z	X → (Y ↔ Z)	_ X → (Y ↔ Z) │ X

 

Лекция №7. Тема: преобразования формул.

Равносильные формулы.

 

Дизъюнктивные и конъюнктивные нормальные формы формул алгебры логики (булевой алгебры).

 

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

 

Пример:

 

Формула, равносильная данной формуле алгебры высказываний и являющаяся конъюнкцией элементарных сумм (дизъюнктивных одночленов), называется конъюнктивной нормальной формой (КНФ), данной формулы.

Например:

– КНФ

 

ДНФ называется дизъюнкция конечного числа элементарных конъюнкций.

- ДНФ

 

КНФ называется конъюнкция конечного числа элементарных дизъюнкций.

- КНФ

 

Равносильные формулы:

 

1) X→Y= Y

 

(X Y) ( )

2) X↔Y=

(X Y) ( )

 

3) Закон Де Моргана ;

4)

5) X↓Y=

 

Примеры:

1.

2.

 

Совершенные СДНФ и СКНФ

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

 

Существует ДНФ (X Y) (

 

Примеры:

СДНФ –

CКНФ -