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

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 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 =?

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

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

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

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

Пример:

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

Например:

– КНФ

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

- ДНФ

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

- КНФ

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

1) X→Y= Y

(X Y) ( )

2) X↔Y=

(X Y) ( )

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

4)

5) X↓Y=

Примеры:

1.

2.

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

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

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

Примеры:

СДНФ –

CКНФ -

Познавательные статьи:



Техника прыжка в длину с разбега

Тактические действия в защите

История Олимпийских игр

История развития права интеллектуальной собственности