ПРЕОБРАЗОВАНИЕ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ. Преобразование логических выражений

• Название: Преобразование логических выражений
• Дата: 20.11.2022
• Размер: 1.9 Mb.
• Имя файла: ПРЕОБРАЗОВАНИЕ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ.ppt
• Тип: Закон; #801409

ПРЕОБРАЗОВАНИЕ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ

ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ И АЛГЕБРЫ ЛОГИКИ

Основные законы алгебры логики

Законы алгебры логики (свойства логических операций) позволяют упростить процесс анализа истинности логического выражения с большим количеством переменных и операций.

Основные законы алгебры логики

Доказательство закона де Моргана


Все законы могут быть доказаны с помощью таблиц истинности.

Основные законы алгебры логики

Распределительный (дистрибутивный) закон (I)


Упростить выражения:A ∨ A & B; A & (A ∨ B)


A ∨ A & B =


A & (A ∨ B) =


A & A ∨ A & B =


A ∨ A & B


= A


= A


A &1 ∨ A & B


= A & (1 ∨ B)


= A & 1

Закон поглощения (II)

A & (A ∨ B) = A

A ∨ 1= 1

Закон поглощения (I)

A ∨ (A & B) = A

Основные законы алгебры логики

Доказательство распределительного (дистрибутивного) закона

Основные законы алгебры логики

Распределительный (дистрибутивный) закон (II)

A ∨ (B & C) = (A ∨ B) & (A ∨ C)

(A ∨ B) & (A ∨ C)


Распределительный
A & (B ∨ C) = (A & B) ∨ (A & C)


A & (A ∨ B) ∨ C & (A ∨ B)


(A ∨ B) & A ∨ (A ∨ B) & C


Переместительный
A & B = B & A


A ∨ C & (A ∨ B)


Поглощения
A & (A ∨ B)=A


Поглощения
A ∨ A & B = A


A ∨ A & C ∨ C & B


Распределительный
A & (B ∨ C) = (A & B) ∨ (A & C)


Доказательство

Логические функции

A

B

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

F16

0

0

0

1

1

0

1

1

0
0
0
0


0
0
0
1


0
0
1
0


0
0
1
1


0
1
0
0


0
1
0
1


0
1
1
0


0
1
1
1


1
0
0
0


1
0
0
1


1
0
1
0


1
0
1
1


1
1
0
0


1
1
0
1


1
1
1
0


1
1
1
1


Логическое выражение может рассматриваться как способ описания логической функции.


0000


0001


Сколько разных функций от двух переменных?


!


Для n = 2 существует 16 различных логических функций.


?


Запишите в общем виде количество различных функций от N переменных.

Логические функции

A

B

F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

F11

F12

F13

F14

F15

F16

0

0

0

1

1

0

1

1

0
0
0
0


0
0
0
1


0
0
1
0


0
0
1
1


0
1
0
0


0
1
0
1


0
1
1
0


0
1
1
1


1
0
0
0


1
0
0
1


1
0
1
0


1
0
1
1


1
1
0
0


1
1
0
1


1
1
1
0


1
1
1
1


Логическое выражение может рассматриваться как способ описания логической функции.


F(A,B)=0


F(A,B)=A & B


?


?


стрелка Пирса (отрицание дизъюнкции, ИЛИ-НЕ)


штрих Шеффера (отрицание конъюнкции, И-НЕ)

A	B	С	F
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

При построении функции можно ориентироваться как на 0, так и на 1 в последнем столбце.


F=1, если во 2-ой, ИЛИ в 3-ей, ИЛИ в 6-ой строке стоят 1.


Запишем выражение в строке так, чтобы была описана только эта строка.


Используя законы логики, можно записать функцию через другие операции.


II способ


Функция от любого количества переменных может быть выражена через функции двух переменных. Любую функцию можно представить через конъюнкцию, дизъюнкцию и отрицание.


Совершенная дизъюнктивная нормальная форма (СДНФ)


Совершенная конъюнктивная нормальная форма (СКНФ)


Функция от любого количества переменных может быть выражена через функции двух переменных.
Любую функцию можно представить через конъюнкцию, дизъюнкцию и отрицание.

A	B	С	F
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

F=0, если во 2-ой ИЛИ в 5-ой строке стоят 0.


Запишем выражение в строке так, чтобы была описана только эта строка:


Запись функции в таком виде можно было получить описывая функцию НЕ F, а затем применяя законы де Моргана.

Вопросы и задания

Упростите логическую формулу:
1.
2.
3.