Математическая логика и теория алгоритмов

1. Математическая логика и теория алгоритмов

Курс лекций

2. 1. Алгебра логики 1.1. Понятие о простом и сложном высказывании

Основным понятием математической логики является
простое логическое высказывание.
Под логическим высказыванием понимают всякое
повествовательное предложение, утверждающее что-либо о
чем-либо и принимающее истинное (И) или ложное (Л)
значение в данных условиях места и времени
Иногда в определении простого высказывания опускают
слова “в данных условиях места и времени”.
Дело в том, что одно и то же высказывание в разных местах
(Земли, континента, страны, города и т.п.), а также в разные
интервалы времени может принимать различные логические
значения.

3.

Пример:
Высказывание: “Сборная команда СССР по баскетболу –
лучшая в мире” для одних промежутков времени является
истинным, а для других ложным. С 1974 по 1978 г. она была
чемпионом мира, поэтому приведенное высказывание было
истинным, если его рассматривать относительно указанного
промежутка времени, и ложным для других промежутков
времени, т.е. тех, когда она не становилась чемпионом мира.
Таким образом, истинность или ложность высказывания
является достаточно условным понятием, и поэтому для
однозначности логического значения высказывания условия
места и времени нужно учитывать.

4.

Существуют, однако, высказывания, которые
всегда и везде являются истинными или ложными
(вечные истины).
Пример:
Высказывание “5 меньше 10” является всегда и везде
истинным, поэтому для такого высказывания условия места и
времени можно не учитывать.
Все простые высказывания, когда они объединяются
грамматическими связками “И”, “ИЛИ”, “если, то…” и др., дают
новые сложные высказывания.
Пример:
2
Высказывание “Если число
иррационально, то
тоже
иррационально” получается связыванием двух простых
высказываний сложным союзом “если…, то…”.
Простые высказывания в дальнейшем будем обозначать
малыми буквами латинского алфавита:
или буквами с индексами: 1 2
Истинное
1
2
значение высказывания будем обозначать цифрой “1”, а ложное
цифрой “0”.
a, b, c,..., x, y, z
x , x ,..., y , y ,...

5. 1.2. Логические операции над высказываниями

Над высказываниями, обозначенными
соответствующими буквами, можно выполнять логические
операции аналогично тому, как выполняются операции
сложения, вычитания, умножения и деления над числами в
арифметике или над буквами в алгебре.
Такими операциями в алгебре логики принято считать:
отрицание (инверсия), конъюнкцию (от лат. conjunctio –
союз, связь; логическое умножение), дизъюнкцию (от лат.
disjunctio – различие, разделение; логическое сложение),
импликацию (от лат.implico – тесная связь), и
эквиваленцию (от лат. aequivalens – равносильный,
равноценный).

6.

х
Отрицанием
(инверсией) называется высказывание x ,
которое является истинным, если высказывание
ложно, и
ложным если высказывание
истинно. Высказывание x ,
читается как “не ” или “неверно, что
”.
х
х
х
х
Таблица истинности для инверсии х ( x )
х
x
1
0
0
1
:

7.

Конъюнкцией двух высказываний x, y называется новое
высказывание, которое считается истинным, если оба
высказывания и
истинны, и ложным, если хотя бы одно из
них ложно.
Конъюнкция высказываний обозначается & у , или x y ,
или x y , или xy и читается “ x и y ”.
x y
x
Таблица истинности для конъюнкции:
х у х& у
0
0
0
1
0
0
1
1
0
1
0
1
Из определения
операций конъюнкции и
отрицания ясно, что
высказывание
&
всегда ложно.
x x

8.

х у
Дизъюнкцией двух высказываний , называется новое
высказывание, которое считается истинным, если хотя бы одно из
высказываний
,
истинно, и ложным, если они оба ложны.
Дизъюнкция обозначается
или
и читается “
или
”.
х у
x y
x y
x
у
Таблица истинност для дизъюнкции:
х
у x y
0
0
0
0
1
1
1
0
1
1
1
1
Из определения операции
дизъюнкции и отрицания ясно,
что высказывание
всегда
истинно.
x x

9.

x, y
Импликацией двух высказываний
называется новое
высказывание, которое считается ложным, если
истинно, а
и истинным во всех остальных случаях.
x, y
x
y – ложно,
x y
у
х y y
x y
Импликация высказываний
обозначается
и читается
“если
то
”, или “из следует ”, или “
влечет ”. Высказывание
называют условием или посылкой, высказывание
- следствием или
заключением, а общее высказывание
- следованием или
импликацией, или условным высказыванием.
x,
y
х
Таблица истинности для импликации:
х
у x y
0
0
1
0
1
1
1
0
0
1
1
1
х

10.

Эквиваленцией (эквивалентностью) двух высказываний называется
новое высказывание
, которое считается истинным, когда оба
высказывания
либо одновременно истинны, либо одновременно
ложны, и ложным – во всех остальных случаях.
Эквиваленция высказываний
обозначается
и читается
“для того, чтобы
необходимо и достаточно, чтобы
”, или “ тогда
и только тогда , когда
”. Эквиваленцию двух высказываний
называют
еще биусловным высказыванием (т.е. двойным условным
высказыванием).
x, y
x,
x, y
xy y
x, y
y
x
x, y
Таблица истинности для эквиваленции:
x
y x y
0
0
1
1
0
1
0
1
1
0
0
1
Операция эквиваленции играет
важную роль как в самой
математике, так и в других
областях деятельности, например в
криминалистике. К ней прибегают в
том случае, когда имеют дело с
высказываниями
и
такими,
что из истинности
следует
истинность и из истинности
следует истинность .
y
x y
x
x
y

11. 1.3.Формулы алгебры логики

Всякое сложное высказывание, которое получается из
простых путем применения приведенных выше операций,
называется формулой алгебры логики. Для сокращения
записей будем (когда это необходимо) обозначать формулы
большими буквами латинского алфавита: A, B, Cи т.д.
Определение 1. Формула A, принимающая истинное значение
при любых комбинациях значений входящих в нее
высказываний, называется тождественно истинной (ТИФ) или
тавтологией и записывается A 1
Определение 2. Формула В, принимающая ложное значение
при любых комбинациях значений входящих в нее
высказываний, называются тождественно ложной (ТЛФ) и
записывается B 0 .
Например:
x x 1 - ТИФ, x x 0 - ТЛФ.

12.

Определение 3. Две формулы A и B алгебры логики называются
равносильными, если они принимают одинаковые логические
значения при всех комбинациях логических значений входящих в них
высказываний. Равносильность, как и тождественность, обозначают
знаком “ ” ( A B )
Например, построив таблицу истинности для высказываний x
.x y можно убедиться, что они являются равносильными
формулами (т.е. последние столбцы для первой и второй формул
будут одинаковыми), т.е. x y x y
y
и
Логическое значение формулы, т.е. истинна она или ложна, зависит не
только от логических значений входящих в нее высказываний, но и от
очередности выполнения входящих в нее операций.
Очередность выполнения операций в формулах, как и в элементарной
алгебре, устанавливается с помощью скобок.
При записи формул можно уменьшить число используемых пар скобок
и тем самым несколько упростить запись формул. Для этого вводятся
соглашения о приоритете одних операций над другими.

13.

Эти соглашения следующие:
1. Операция отрицания является наиболее приоритетной среди других
операций. Поэтому можно не заключать в скобки формулу или часть её,
стоящую под знаком отрицания. Тогда вместо записи ( x y z ) можно
писать x y z .
2. Считается, что знак операции конъюнкции связывает высказывания
формулы “сильнее” знаков , , т.е. вместо ( x y ) z пишем
,x y z , вместо ( x y ) z пишем x y z ,и вместо
(. x y ) ( z s) пишем x y z . s
связывает высказывания сильнее, чем знаки
и , т.е. вместо ( x y ) z можно писать x y z , а вместо
.( x y ) z можно писать x y z .
3. Считается, что знак
4. Считается, что знак сильнее связывает высказывания, чем знак
, т.е. вместо
( x y) z
пишем
x y z.
5. Можно опускать внешние скобки, которые содержат внутри себя
остальные символы, составляющие формулу. Так, формулу
( x ( y z )) можно писать x ( y z ).

14.

Приведенные соглашения значительно упрощают запись формулы.
Так, например, формула (( x y ) z ) (( x y ) z ) ,
записанная с учетом сказанного выше, будет выглядеть так :
4
5
6
2
3
1
x y z ( x y z )
Расстановку цифр над операциями в формуле, обозначающих
последовательность их выполнения, назовем разметкой формулы.
Введенные соглашения и разметка исходной формулы очень помогает при
составлении таблиц истинности. Приведем порядок составления таблиц
истинности сложного высказывания. Сначала нужно определить
приоритеты выполнения операций. Затем, исходя из количества
простых высказываний, входящих в сложное высказывание, выписывают
всевозможные комбинации логических значений этих высказываний.
Количество комбинаций определяет число строк таблицы истинности, и
для двоичных комбинаций оно равно 2 n , где
– число различных простых
высказываний.
Количество столбцов таблицы истинности определяется суммой чисел
последовательно выполняемых операций и простых высказываний.
n

15.

Рассмотрим пример:
Составить таблицу истинности для сложного высказывания
( x x) ( y ( x z ))
Выполним сначала разметку заданной формулы.
В результате получим:
1 2
5
4
3
( x x) ( y ( x z ))
Так как простых высказываний 3, то число строк в таблице истинности
будет 8 , и число столбцов тоже будет 3 5 8 .

16.

Таблица истинности для формулы
x y z
( x x) ( y ( x z ))
:
x x x x z y ( x z) ( x x) ( y ( x z))
(1)
0 0 0 1
(2)
1
(3)
1
(4)
1
(5)
1
0 0 1
1
1
1
1
1
0 1 0
0 1 1
1
1
1
1
1
1
1
1
1
1
1 0 0
1 0 1
0
0
1
1
0
1
1
1
1
1
1 1 0
0
1
0
0
0
1 1 1
0
1
1
1
1

17. 1.4. Аксиомы и законы алгебры логики

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

18.

I. Аксиомы одиночных элементов:
1)
3)
x 1 1;
x 1 x;
2)
4)
x 0 x
x 0 . 0
II. Аксиомы и законы отрицания:
1) x x ; 2) x x 0 (закон противоречия);
3) x x 1(закон исключенного третьего);
4) x1 x2 x1 x2
; 5) x1 x2 x1 x2 (законы де Моргана).
III. Комбинационные законы:
1) x x x (общий случай
2)
(общий случай
x x x
3) x1 x 2 x 2 x1
4) x1 x 2 x 2 x1
x x .... x x );
x x .... x x
– законы
идемпотентности
);
- переместительные законы
5) x1 ( x 2 x 3 ) x 2 ( x1 x 3 ) x 3 ( x1 x 2 )
6) x1 ( x 2 x 3 ) x 2 ( x1 x 3 ) x 3 ( x1 x 2 )
–
сочетательные
законы.

19.

7) x1 ( x2 x3 ) x1 x2 x1 x3 – распределительный
(дистрибутивный) закон первого рода;
8) x1 ( x2 x3 ) ( x1 x2 ) ( x1 x3 ) – распределительный
(дистрибутивный) закон второго рода.
Пример:
Возьмем правую часть закона 8) и выполним логическое
перемножение скобок:
x1 x2 x1 x3 x1 x1 x1 x3 x2 x1 x2 x3 x1 x1 x3 x1 x2 x2 x3 x1
(1 x3 ) x1 x2 x2 x3 x1 x1 x2 x2 x3 x1 (1 x2 ) x2 x3 x1 x2 x3.

20.

IV. Некоторые важные равносильности:
1) x y x y; 2) x y ( x y ) ( y
3)
x y x y;
;x)
x y x y .
4)
V. Закон двойственности.
А
Пусть формула
содержит только операции конъюнкции,
дизъюнкции и отрицания. Операцию конъюнкции называют
двойственной операции дизъюнкции, и наоборот.
Определение. Формулы
*
*
A A называются двойственными,
и
если формула A получена из формулы
ней каждой операции на двойственную.
Например:
А путем замены в
A ( x y ) z, A ( x y) z.

21.

Свойства операций импликации и эквивалентности,
вытекающие из приведенных выше равносильностей,
следующие:
1. Операция импликации не обладает переместительным
свойством (законом).
Действительно: x y x
видим, что x y
y x.
y, y x y x.Отсюда
2. Операция импликации не обладает сочетательным свойством
(законом).
x ( y z) x y z ,
x ( z y ) x z y y ( x z ) y x z;
y ( z x) y z x , z ( x y ) z x y ,
z ( y x) z y x .
Действительно:

22.

3. Операция эквивалентности обладает переместительным
свойством.
Действительно, на основании равносильностей IV.2 и IV.1
имеем: x y ( x y ) ( y x) ( x y ) ( y x);
y x ( y x) ( x y) ( y x) ( x y).
4. Операция эквивалентности обладает сочетательным
свойством.
Действительно, построив таблицы истинности или выполнив
соответствующие преобразования, можно показать, что
выполняются равносильности:
x ( y z ) ( x y ) z ( x z ) y ( y x) z ( y z ) x ( z
x) y ( z y) x.

23.

Алгебраические преобразования исходной формулы
можно выполнять тремя способами:
1) от начала к концу, т.е. сначала выполнять наиболее
приоритетные операции, двигаясь к менее приоритетным;
2) от конца к началу, т.е. двигаясь от менее приоритетных к
более приоритетным операциям;
3) комбинируя предыдущие два способа.

24.

Приведём пример упрощения формулы, используя прямой
порядок выполнения операций:
3
2
1
5
4
x y xy x y ( x ( y ( xy))) ( x y)
Используя правило поглощения y xy y , получаем формулу:
3
5
4
( x y ) ( x y )
Выполняя операцию с номером 5, будем иметь ( x y ) ( x
Остается выполнить операцию отрицания. Выполнив её,
используя закон де Моргана, получим формулу
y)
xy x y.

25.

Приведём последовательное упрощение той
же формулы, используя обратный порядок
выполнения операций.
В формуле
( x y xy) ( x y )обозначим
x y xy , A
x y Bи будем выполнять операцию импликации над
А и В:
A B A B x y xy ( x y )
Снимем отрицание, применяя закон де Моргана, и получим формулу
x y x y ( x y ).
Снимая групповое отрицание
x y
x y ( x y ) ( x y ).
получим формулу:
Применяя операцию конъюнкции к скобке, получим:
x y x x y y x y.
Используя аксиомы x x ... x x, x x ... x x,
получим формулу: x y x y.

26.

Если любую формулу алгебры логики можно свести к некоторой другой
равносильной формуле, содержащей только определенную систему операций,
то такая система операций называется функционально полной системой
операций (ФПСО) или базисной. В алгебре логики такой ФПСО являются
системы операций:
{ , , }, { , }{ , }
Покажем на примере, как логическая формула сводится к другой равносильной ей
формуле, но содержащей только указанные системы операций.
x y xy x y x y x y
Сведем правую формулу приведенной равносильности к формуле, содержащей
только операции
{ , }.
К формуле
x y x y применим аксиому x x . Тогда:
x y x y x y x y x y x y x yx y
x y x y
Таким образом, если говорят об упрощении формулы, то имеют в виду ее сведение к
ФПСО.

27. 1.4.1. Правила склеивания для элементарных конъюнкций и дизъюнкций

Логическое произведение/сумма любого числа высказываний называется
элементарным, если сомножители/слагаемые в нем являются либо
одиночными высказываниями, либо их отрицаниями
Например: x1 x2 x4 – элементарное произведение,
– неэлементарное произведение.
x x x
1
2
4
Количество сомножителей в элементарном произведении называется его
рангом.
r
Два элементарных произведения одинакового ранга называются
соседними, если они являются формулами одних и тех же
высказываний и отличаются знаком отрицания только одного
высказывания.

28. Правило склеивания для элементарных конъюнкций:

Логическую сумму двух соседних произведений некоторого
ранга r можно заменить одним элементарным произведением
ранга r 1 , являющимся общей частью исходных слагаемых.
Пример:
x1 x 2 x4 x5 x1 x2 x4 x5 x1 x4 x5 .
Правило склеивания для элементарных дизъюнкций:
Логическую сумму двух соседних произведений некоторого
ранга r можно заменить одним элементарным произведением
ранга r 1, являющимся общей частью исходных слагаемых.
Пример: ( x1
x2 x3 x6 )( x1 x2 x3 x6 ) x1 x3 x6 .

29. 1.4.2. Правила поглощения для элементарных конъюнкций и дизъюнкций

Правило поглощения для элементарных конъюнкций:
Логическую сумму двух элементарных конъюнкций разных
рангов, из которых одна является частью другой, можно
заменить слагаемым, имеющим меньший ранг.
Пример: x1 x2 x3 x6 x2 x3 x2 x3
Правило поглощения для элементарных дизъюнкций:
логическое произведение двух элементарных дизъюнкций
разных рангов, одна из которых является частью другой, можно
заменить сомножителем меньшего ранга.
Пример: ( x1 x 2 x 4 x 5 )( x1 x 5 ) x1 x 5
Правила склеивания и поглощения, как не трудно заметить,
являются следствиями распределительных знаков.

30. 1.4.3. Правило развёртывания

Это правило также является следствием распределительных
законов и регламентирует действие, обратное склеиванию. Оно
используется, когда нужно составить некоторое логическое
выражение в виде совокупности конституент единицы (КЕ) или
конституент (КН) нуля.
Конституента единицы – это конъюнкция всех
высказываний,
которые входят в неё в прямом или инверсном виде лишь по
одному разу и обращающаяся в ноль при одном наборе логических
значений высказываний и в единицу при всех остальных наборах.
Количество KE и КН заданного числа
высказываний совпадает,
как это следует из определения, с числом различных наборов
высказываний и равно 2n . Конституенты принято обозначать
1
0
какими-либо символами, например: Ci и Ci . Единица или ноль в
верхнем индексе означает вид конституенты, т.е. КЕ это или КН,
нижний индекс означает ее номер, совпадающий с номером набора.
n
n

31. Все КЕ для двух высказываний:

Высказыван
ия
КЕ
x1
x2
0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1
C 01
х1 х 2
C11
1
1
C
x
х
C
х1 x 2 2
1 2
3 x1 x2

32. Все КН для двух высказываний:

Высказыв
ания
КН
x 1 x2
C00 x1 x2 C10 x1 х 2 C 20 х1 x 2 C 30 х1 х 2
0
0
0
1
1
1
0
1
1
0
1
1
1
0
1
1
0
1
1
1
1
1
1
0

33. Развёртывание элементарных конъюнкций

r
1. В развертываемую элементарную конъюнкцию ранга
вводятся в качестве дополнительных сомножителей n rединиц,
где n – число высказываний и n r
2. Каждая единица представляется в виде xi xi 1, где
–
i
высказывание, отсутствующее в исходной конъюнкции.
3. Производится раскрытие всех скобок на основе
распределительного закона 1-го рода, что приводит к
развертыванию исходной конъюнкции ранга
в логическую
n r
сумму
КЕ.
Пример: Развернуть конъюнкцию A x x 2 x . Здесь
1
5
предполагается, что число высказываний n 5 , но два из них
отсутствуют, тогда:
1) A x1 x2 1 1 x5
2) A x1 x2 ( x3 x3 )( x4 x4 ) x5
3) A x1 x2 x3 ( x4 x4 ) x5 x1 x2 x3 ( x4 x4 ) x5
x
2
r
x1 x2 x3 x4 x5 x1 x2 x3 x4 x1 x2 x3 x4 x5 x1 x 2 x3 x4 x5

34. Развёртывание элементарных дизъюнкций

1. В развертываемую дизъюнкцию ранга r вводится n-r нулей.
2. Каждый нуль представляется произведением xi xi 0,
где х i – высказывание, отсутствующее в исходной дизъюнкции.
3. Полученная сумма преобразуется с помощью
распределительного закона 2-го рода в логическое
произведение 2n r КН.
Пример: Развернуть дизъюнкцию A x1 x3 . Здесь число
высказываний n 3 , отсутствует высказывание x 2 :
A x1 x3 x2 x2 ( x1 x3 x2 )( x1 x3 x2 ).

35. 1.5. Функции алгебры логики. Нормальные формы логических функций

Логическая функция [функция алгебры логики (ФАЛ)]
f ( x1 , x2 ,..., xn ) – это выражение, представляющее собой
сложное высказывание, состоящее из нескольких простых
высказываний x1 , x 2 ,..., x n , связанных соединительными
словами. Это сложное высказывание принимает значения 0 или
1 на всех наборах логических значений всех простых
высказываний.
Набор логических переменных, или, иначе, входной набор – это
определенная комбинация значений переменных в логической
функции. Максимальное число различных входных наборов
n
есть величина m 2 , где
– число переменных.
n

36.

Полностью определенная функция – это логическая функция,
принимающая значение 0 или 1 на всех входных наборах.
Частично определенная функция – это логическая функция,
значения которой определены не на всех входных наборах. Такие
наборы называют безразличными.
Частично определенную логическую функцию можно сделать
полностью определенной, приписав безразличным наборам
произвольные значения: 0 или 1.

37. В алгебре логики каноническими принято считать нормальную дизъюнктивную форму (НДФ) и нормальную конъюнктивную форму (НКФ) и соответствен

В алгебре логики каноническими принято считать
нормальную дизъюнктивную форму (НДФ) и нормальную
конъюнктивную форму (НКФ) и соответственно
совершенную НДФ (СНДФ) и совершенную НКФ (СНКФ).
НДФ – это дизъюнкция нескольких элементарных конъюнкций.
СНДФ – форма, все члены которой имеют высший ранг, являясь
конституентами единицы или нуля
Общая запись любой логической функции в СНДФ имеет вид:
2 n 1
1, если f на i м наборе равна1,
1
ki
i
i
i 0
0, если f на i м наборе равна 0.
f
(k c )
1
f
C
Иначе говоря, значение k i определяет факт вхождения
iв .
1
Приki 1 конституента C входит в f , а при k i 0 – не входит.
i

38. Пример: По заданной таблице истинности составить СНДФ функций

f1 x1 x 2 ,
x 1 x2 f 1 f 2
0
0
0
1
0
0
0
1
1
1
0
1
0
1
1
0
f 2 x1 x2 x1 x 2.
Общая запись любой логической функции в СНКФ имеет вид:
f
2 n 1
(k
i 0
i
c )
0
i
0, если f на i м наборе равна 0,
ki
1, если f на i м наборе равна1.
Иначе говоря, в СНКФ будет отсутствовать тот дизъюнктивный
член, для которого ki 1.

39.

СНКФ для выше приведенной таблицы истинности будут иметь
вид :
f1 ( x1 x2 ) ( x1 x2 ) ( x1 x2 )
f 2 ( x1 x 2 ) ( x1 x 2 )
В общем случае переход к СНДФ и СНКФ осуществляется за три
шага.
1. Путем многократного применения закона отрицания снимаются
групповые и общие отрицания так, чтобы они оставались только у
одиночных переменных.
2. С помощью распределительных законов производится переход к одной
из нормальных форм функций:
а) для перехода к НДФ применяется распределительный закон первого
рода [раскрываются скобки, т.е. x1 ( x2 x3 ) x1 x2 x1 x3 ];
б) для перехода к НКФ применяется распределительный закон второго
рода [вводятся скобки, т.е x1 x2 x3 ( x1 x2 )( x1 x3 )] ;
3. С помощью правила развертывания производится преобразование
членов НДФ или НКФ в соответствующие конституенты.

40.

Пример: Преобразовать функцию
в СНДФ и СНКФ.
f ( x1x2 x1x2 ) x3 x1x2
1. Применяя законы инверсии, снимаем все групповые отрицания:
f ( x1 x2 x1 x2 ) x3 x1 x2 ( x1 x2 x1 x2 ) x3 x1 x2 ( x1 x2 )( x1 x2 ) x3 x1 x2
2. Применяя распределительный закон 1-го рода, получаем:
f НДФ ( x1 x 2 )( x1 x 2 ) x3 x1 x 2 x 1 x1 x3 x1 x 2 x3 x1 x 2 x3 x 2 x 2 x3 x1 x 2
0
0
x1 x 2 x3 x1 x2 x3 x1 x2 .
Применяя распределительный закон 2-го рода к формуле, полученной после
первого шага, будем иметь:
f НКФ ( x1 x2 )( x1 x2 ) x3 x1x2 (( x1 x2 )( x1 x2 ) x3 x1 )(( x1 x2 )( x1
x2 ) x3 x2 ) ( x1 x1 x2 )( x1 x1 x2 )( x1 x3 )( x2 x1 x2 )( x2
x1 x 2 )( x 2 x3 ) ( x1 x 2 )( x1 x3 )( x1 x3 )( x1 x 2 )( x 2 x3 ) ( x1 x 2 )( x1
x3 )( x 2 x3 ).

41.

3. Применяя правило развертывания, переходим от НДФ к СНДФ и от
НКФ к СНКФ:
f СНДФ x1 x2 x3 x1 x2 x3 x1 x2 ( x3 x3 ) x1 x2 x3 x1 x2 x3 x1 x2 x3 x1 x2 x 3.
f СКНФ (x1 x2 x3 x3 )( x1 x2 x2 x3 )( x1 x1 x2 x3 ) ( x1 x2 x3 )( x1
x2 x3 )( x1 x2 x3 )( x1 x 2 x3 )( x1 x2 x3 )( x1 x2 x3 ) ( x1 x2 x3 )
( x1 x2 x3 )( x1 x2 x3 )( x1 x2 x3 ).
Переход от одной формы логической функции к другой можно
осуществить, используя таблицу истинности. Для этого надо по
заданной формуле построить таблицу истинности. Для в всех 1
в столбце функции составить КЕ, соединив их знаком
. Для
всех 0 в столбце функции составить КН, заключив их в скобки и
поставив между ними знак
.

42. 1.6.Минимизация логических функций

К настоящему времени разработано достаточно большое число методов и
приемов минимизации логических функций. Наиболее известными и
распространенными среди них являются:
1) расчетный метод – метод непосредственных логических
преобразований;
2) табличный метод – метод карт Карно или Вейча – Карно;
3) расчетно-табличный метод Квайна.

43.

Исходной формой для любого из этих методов является одна из
совершенных нормальных форм СНДФ или СНКФ. В общем
случае любой из упомянутых методов состоит из трех этапов:
1. Переход от СНД(К)Ф к сокращенной сНД(К)Ф путем
выполнения всех возможных склеиваний друг с другом сначала
конституент, а затем всех членов сумм (произведений) более
низкого ранга до тех пор, пока склеивание возможно.
2. Переход от сНД(К)Ф к тупиковой нормальной
дизъюнктивной (конъюнктивной) форме (ТНД(К)Ф) путем
устранения избыточных импликант.
3. Переход от ТНД(К)Ф к минимальной форме (МНД(К)Ф)
логической функции.

44. 1.6.1. Расчетный метод минимизации

Каждый из конкретных методов минимизации состоит из тех же трех
шагов, что указывалось выше. Но эти шаги в каждом методе могут иметь
свою особенность:
1.Склеивание всевозможных членов исходной СНД(К)Ф, т.е.
сначала конституент, затем импликант ранга n - 1 и т.д., пока
склеивание возможно.
2.Проверка каждой простой импликанты в СНД(К)Ф на избыточность с
целью её удаления.
3. Упрощение полученной ТНД(К)Ф путем применения операции
отрицания и распределительного закона 1-го или 2-го рода.

45.

Пример: Минимизировать функцию
f сНДФ x1 x 2 x3 x1 x 2 x3 x1 x 2 x3 x1 x 2 x3 .
1. Выполняя склеивание, получим сНД(К)Ф:
f сНДФ x1 x3 x 2 x3 x1 x 2
2.Удаляем избыточные импликанты : x1 x3 1на наборе x1 0, x3 1,
так как x2 1 1 x2 1, , то импликанта x1 x3 - избыточная;
x2 x3 1 на наборе x2 0 ; x3 1 , а так как x1 1 0 x1 x1,
то импликанта x2 x3 не является избыточной, x x 1
на наборе x 0, x 1 , а так как 1 x 0 1 x 2 x , то
1
2
3
3
3
не
является
избыточной.
x1x2
Таким образом, отбросив избыточную импликанту, получим ТНДФ:
Таким образом, отбросив избыточную импликанту, получим ТНДФ:
f ТНДФ x 2 x3 x1 x 2
3. Дальнейшему упрощению функция не поддается.

46. 1.6.2. Табличный метод минимизации

В этом методе два первых шага как бы объединены и выполняются с
помощью специальной таблицы, называемой картой Карно (КК) или
картой Карно-Вейча (еще иногда называемой диаграммой). Третий шаг
выполняется так же, как и в расчетном методе.
Карта Карно для двух переменных :
f x1 x 2
f x1 x 2 x1 x 2
x1 x 2 .

47.

Карта Карно для 3 – х переменных:
Следует отметить
особенность нумерации
клеток. Их нужно
нумеровать так, чтобы
две рядом
расположенные клетки
отличались значением
всего лишь одного
разряда.
Процесс получения
отраженных кодов (код
Грэя) мы можем
представить
так :

48.

Для 3-разрядных двоичных чисел двоичный отраженный код формируется
следующим образом:
Для четырех переменных КК содержит 16 клеток

49.

Для пяти переменных необходимо иметь КК с 32 клетками. Эти 32
клетки можно представить как 2 карты по 16 клеток или одну карту на 32
клетки. Одна карта на 32 клетки будет иметь такую нумерацию строк и
столбцов с учетом использования отраженных кодов, которая показана на
рисунке:
В карте Карно, изображенной на рис.6, нумерация клеток дается в
десятичной системе счисления. Это позволяет производить очень
компактную запись логической функции

50.

Пример:
Если логическая функция записана в
виде y
(0,1,3,4,6,9,11),
то это значит, что число клеток будет
l 2 m , m [log 2 11] [3,47] 4
т.е. число переменных
будет 4, число
4
клеток будет l 2 16,
а единицы надо поместить в клетки с
номерами 0,1,3,4,6,9,11.
В двоичной системе счисления эти
номера будут иметь вид:
0000,0001,0011,0100,0110,1001,1011.
Тогда КК с отображенной на нее
приведенной функцией будет
иметь вид:

51. Правила минимизации с помощью карт Карно

k
1. 2 соседних клеток, содержащих 1, и расположенных по
вертикали либо по горизонтали в виде прямоугольника либо
квадрата (такую совокупность клеток называют покрытием),
соответствуют одной импликанте, ранг которой r n k ,где
− число переменных, меньше ранга покрываемых конституент
на
единиц. Чем больше клеток в покрытии, тем проще
выражаемый этим покрытием член логической функции −
импликанта.
2. Импликанта, соответствующая некоторому покрытию
заполненных единицами клеток, содержит символы тех
переменных, значения которых совпадают у всех клеток,
образующих покрытие. Причем символ берется с отрицанием,
если для всех клеток покрытия он принимает значение 0, и без
отрицания – в противном случае.
n
k

52.

Пример 1: Минимизировать логическую функцию
y
(1,2,3,5,7)
с помощью КК. Минимизируемая функция будет состоять из трех
переменных, соответствующая ей КК будет состоять поэтому из 8 клеток.
покрытие 1
покрытие 2
x1
x2
x3
x1
x2
x3
0
0
1
0
1
1
0
1
1
1
0
1
1
1
x3
1
x2
0
1
0
x1

53.

Следует отметить некоторые особенности работы с покрытиями. Каждое
покрытие нужно использовать только один раз. Если КК свернуть в
цилиндр вдоль горизонтальной или вертикальной оси, то будет видно,
что крайние клетки тоже оказываются соседними и они могут
образовывать покрытие.

54.

Пример 2:
КК с отображенной на нее логической функцией, когда единицы
находятся в крайних клетках. Эта функция имеет вид y (0,2,3,4,5,6)
х1
х2
х3
x1
x2
x3
x1
x2
x3
0
0
0
0
1
1
1
0
0
0
1
0
1
0
0
0
x1
1
x2
0
1
x1
0
x2
1
1
1
0
х3
Результат минимизации:
y x3 x1 x2 x1 x2 .

55. 1.6.3. Расчётно-табличный метод минимизации (метод Квайна)

Минимизация этим методом отличается от расчетного только способом
выявления избыточных членов в сНДФ. Данный метод предложен
американским ученым Квайном, и поэтому называется его именем.
Его удобно рассматривать в виде алгоритма с комментариями.
Считаем, что минимизируемая логическая функция приведена к
СНДФ.
1.
Переход от СНДФ к сНДФ. Отыскиваются все простые импликанты.
Для этого выписываются все конституенты и все их пары исследуются
на возможность склеивания друг с другом. Конституенты,
участвующие хотя бы в одном склеивании, отмечаются, но не
исключаются из дальнейших сравнений. В результате выявляются
импликанты, содержащие по (n-1)-й переменной. С полученными
импликантами выполняется та же процедура, что и с исходными
конституентами. В результате выявляются импликанты, содержащие
n-2 переменные, и так продолжается до тех пор, пока членов,
допускающих склеивание, не останется. Все не отмеченные в
процессе указанного преобразования члены представляют собой
простые импликанты.

56.

2.
3.
Переход от сНДФ к ТНДФ. Дизъюнкция всех простых импликант может
содержать избыточные импликанты. Поэтому их надо исключить. Для
этого составляется импликантная таблица, строки которой
обозначаются выявленными на 1-м шаге простыми импликантами, а
столбцы – конституентами, входящими в СНДФ исходной функции.
Расстановка меток. Любая клетка импликантной таблицы отмечается,
например, цифрой 1, если она попадает на пересечение конституенты
и импликанты, полностью входящей в конституенту. В каждом столбце
при этом может оказаться по нескольку отмеченных клеток. Задача
упрощения НДФ сводится к вычеркиванию из таблицы максимального
количества строк таким образом, чтобы после этого в каждом столбце
осталась, по крайней мере, одна отмеченная клетка.

57.

4.
5.
6.
Выделение ядра Квайна (существенных импликант).
Выявляются и вычеркиваются столбцы, содержащие только по
одной отмеченной клетке. Простые импликанты,
соответствующие этим клеткам, вносятся в окончательное
выражение НДФ как обязательные члены. Если таких
столбцов нет, то переход к п.5, если же есть, то в таблице
зачеркиваются строки, соответствующие обязательным
простым импликантам и столбцы, содержащие отмеченные
клетки в вычеркнутых строках.
Поглощение (сжатие) столбцов. Если после этого в таблице
окажутся такие пары столбцов, что все отмеченные клетки i-го
столбца совпадают полностью или частично с клетками j-го
столбца, то j-й столбец вычеркивается. Если таких пар
столбцов нет, то переход к п.7, иначе – к п.6.
Вычеркивание пустых строк. Строки, не содержащие после
выполнения п.п. 4 и 5 ни одной отмеченной клетки, также
вычеркиваются.

58.

Поглощение (сжатие) строк. Если в таблице имеется такая
пара строк, что все отмеченные клетки k-й строки совпадают
полностью или частично с отмеченными клетками l-й строки,
то k-я строка вычеркивается. Если таких строк нет, то переход
к п.8
8.
Получение МНДФ. Для этого импликанты ядра Квайна, т.е.
полученные в п. 4 и оставшиеся не вычеркнутыми после
выполнения п. 7, соединяются знаками дизъюнкции.
Пример:
Минимизировать логическую функцию четырех переменных,
заданную в числовой форме . Так как наша цель –
рассмотрение процесса преобразования импликантной
таблицы, то п. 10 алгоритма выполнять не будем, а выпишем
готовые импликанты. Их совокупность будет иметь вид
7.
{01 , 111,111 ,0 0 , 0 0, 00,1 0}
Прочерки в импликантах указывают на отсутствие в них
соответствующей переменной.

59.

В табл. 9 вертикальные и горизонтальные линии, пересекающие
соответствующие столбцы и строки, пронумерованы цифрами. Эти
цифры указывают на порядок вычеркивания столбцов и строк.
В соответствии с п.4 алгоритма устанавливаем, что импликанты 0–0– и –
0–0 являются существенным для конституент
0000,0001,0100,0101 и 0000, 0010,1000,1010. Они должны быть внесены
в МНДФ. Поэтому вместе со 2-м и 3-м столбцами, как содержащими
всего по одной отмеченной клетке, вычеркиваем 4-ю и 5-ю строки, а
также столбцы 1,4,5,7 и 8, на пересечении с которыми в вычеркнутых
строках 4 и 5 стоят единицы.

60.

В результате выполнения этих операций импликантная таблица
приобретает вид:
Далее выполняем поглощение столбцов. Однако это невозможно,
так как в таблице нет ни одной пары столбцов, которые бы
полностью или частично совпадали. Поэтому в соответствии с п.7
алгоритма выполняем поглощение строк. Видим, что строка 2
поглощает строку 1, а строка 5 – строку 4.

61.

В результате получаем таблицу:
Снова выполняем поглощение столбцов и получаем таблицу:

62.

Так как в предыдущей таблице получили строку, не содержащую
единиц, то, вычеркивая её, получаем окончательную таблицу:
Соединяя импликанты, соответствующие столбцам с одной
отмеченной клеткой и оставшиеся в последней таблице, знаком ,
получим МНДФ:
y x1 x3 x2 x4 x2 x3 x4 x1 x4 .
Достоинством рассмотренного метода Квайна является то, что он
применим для любого числа переменных и может быть
реализован в виде программы для ЭВМ.
В качестве недостатка можно отметить его относительную сложность.

63.

1.7 Некоторые применения алгебры логики
Использование алгебры логики при создании РКС основано на том, что в
них основным техническим элементом является электромагнитное реле,
имеющее два устойчивых состояния (включено/выключено). При
включенном состоянии ток в цепи, в которой стоит реле, протекает через
его контакты и не протекает при выключенном состоянии. Включенному
состоянию сопоставляют цифру 1, а выключенному – цифру 0.
Исходя из этого, оказалось возможным каждой РКС поставить в
соответствие некоторую формулу (логическую функцию), а каждой
формуле – некоторую РКС. Тогда изучение свойств РКС и ее упрощение
можно заменить изучением и упрощением соответствующей формулы.
Затем от упрощенной формулы можно перейти к схеме.

64.

Простейшая РКС содержит один переключатель P, имеет один вход А и один
выход В. Переключателю Р можно поставить в соответствие высказывание
“переключатель Р замкнут”.
Если высказывание Р истинно, то сигнал, поступающий на вход А появится
на выходе В. В этом случае схема проводит ток. Если высказывание Р ложно,
то схема ток не проводит и на выход В сигнал не пройдет.
Таким образом, наше высказывание можно представить простейшей РКС:
или
А)
Б)
Отрицанием высказывания “переключатель Р замкнут” будет
высказывание “переключатель Р разомкнут” и этому высказыванию будет
соответствовать РКС:
или
А)
Б)

65.

Если два переключателя соединить последовательно, то такая РКС
будет проводить ток лишь в одном случае, а именно тогда, когда оба
переключателя P и Q замкнуты:
или
А)
Б)
В других трех случаях: “P замкнут и Q разомкнут”, “P разомкнут и Q
замкнут”, “P замкнут и Q разомкнут” ток со входа А поступать на вход В не
будет. А это есть не что иное, как конъюнкция высказываний P, Q, т.е.
P Q
Аналогичные рассуждения приводят к тому, что параллельная РКС,
является дизъюнкцией P Q
или
А)
Б)

66.

Если высказывание P есть отрицание высказывания P, то РКС будет
проводить ток всегда (какой-либо из контактов будет постоянно замкнут,
и ток со входа А будет протекать на выход В либо через верхний контакт,
либо через нижний). Такая схема соответствует тождественно истинной
формуле
или
Б)
А)
Тождественно ложной формуле P P
, очевидно, будет
соответствовать РКС , которая ток никогда не проводит, так как в ней
один из контактов всегда разомкнут:
или
А)
Б)

67.

Из схем, приведенных выше, путем последовательного и
параллельного их соединения могут быть построены РКС любой
сложности.
Обоснованием этого утверждения является то обстоятельство, что
любая формула алгебры логики путем равносильных преобразований
может быть представлена в одном из базисов: { , , },{ , },{ , }.
Рассмотрим примеры представления формулы в виде РКС, упрощение
этой формулы и последующее представление ее в виде схемы.
Пример 1. f1 ( x y) ( x y) Этой формуле соответствует схема:

68.

Пример 2. f2 ( x y z) ( x y z) ( x y z) ( x y z )
Этой формуле соответствует схема:
Упростим формулу, f 2 введя в нее 2 дополнительные конъюнкции xyz(формула
f 2 от этого не изменится на основании комбинационного закона III.1) и объединив
каждую из конъюнкций xyz со 2 , 3 и 4-м членами формулы f 2
f 2 (( xyz) ( xyz)) (( xyz) ( xyz)) (( xyz) ( xyz )) yz xz xy z( x y) xy.

69.

Последней формуле будет соответствовать схема:
Как нетрудно заметить, последняя РКС значительно проще исходной. В
дальнейшем при изображении схем, с целью упрощения их начертания,
переменные мы не будем заключать в прямоугольник, а будем их писать в
разрыве линий. Тогда, например, предыдущая схема изобразится так:
Рассмотренные РКС, используются главным образом, в устройствах и
установках сильноточной техники, т.е. там, где через контакты реле
протекают относительно большие токи. Еще большее значение аппарат
алгебры логики имеет для элементов и устройств слаботочной техники , т.е.
там где протекают малые токи. Такой техникой является микроэлектроника,
благодаря достижениям которой созданы современные компьютеры,
мобильные телефоны и множество других аппаратов, куда встраиваются
микропроцессоры и различного рода цифровые автоматы.

70.

Последние же строятся на основе цифровых логических схем,
реализуемых в базисах операций { , , },{ , },{ , }. Поэтому рассмотрим
связь между формулами алгебры логики и соответствующими цифровыми
логическими схемами.
Будем считать, что каждая переменная в формуле алгебры логики
соответствует одному входу в некоторой логической схеме. Над одной
переменной x в алгебре логики, как мы знаем, может выполняться
единственная операция отрицания. Для реализации операции отрицания
логической схемой необходимо, чтобы эта схема имела один вход x и
один выход x , и в виде схемы это будет выглядеть так:
или
Такая схема называется инвертором или схемой НЕ. Она инвертирует
сигнал, т.е. переворачивает фазу сигнала на 180 0 (иначе говоря, если мы
подадим на вход инвертора сигнала x 0 , то на его выходе появится
сигнал x 1 ).

71.

Если в формуле имеется две и более переменных, связанных
операцией конъюнкции, то в соответствующей логической схеме мы
должны иметь два и более сигнальных входа и один выход, а сама схема
будет называться по имени операции, соединяющей эти переменные в
формуле. Тогда конъюнкция и дизъюнкция двух переменных в виде схем
будут выглядеть так:
или
или
Логическая схема, реализующая операцию конъюнкции, называются
схемой совпадения (единичный сигнал на выходе схемы появится лишь
тогда, когда оба единичные сигнала на входе совпадут по времени, т.е. оба
примут единичное значение), схемой И или конъюнктором.
Логическая схема, реализующая операцию дизъюнкции, называется
схемой объединения (единичный сигнал на ее выходе появится тогда,
когда он появится хотя бы на одном из ее входов), схемой ИЛИ, или
дизъюнктором.
При числе входов, т.е. переменных, больше двух соответствующие
схемы будет отличаться от приведенных выше лишь числом входов и они
будут называться соответственно: 2-входовая, 3-входовая и т.д. n-входовая
схемы И, 2-входовая, 3-входовая и т.д. n-входовая схемы ИЛИ.

72.

Если над некоторым числом переменных, соединенных операцией или .
выполняется операция отрицания, то начертание логических схем будет
выглядеть так:
На вход логической схемы могут подаваться уже инвертированные
сигналы. Тогда 3-входовые схемы И и ИЛИ будут соответственно такие:
Опираясь на приведенное соответствие между формулами алгебры логики
и логическими схемами, рассмотрим некоторые примеры перехода от
формул к схемам и наоборот.

73.

Пример. Представить формулу
x1 x2 x3 x1x2
в виде логической
схемы,
упростить эту формулу и нарисовать соответствующую ей схему.
Решение:
Упростим исходную формулу:
x1 x2 x3 x1x2 x1 x2 x3 x1x2 x1 ( x2 x3 x2 ) x1 ( x2 x2 )( x2 x3 ) x1 ( x2 x3 )
Соответствующая этой формуле схема будет иметь вид:

74.

При переходе от схемы к формуле её удобно сначала разметить, т.е.
обозначить все выходы какими-либо символами (например, большими
буквами латинского алфавита A,B,C,…). Затем, двигаясь от последнего
выхода к началу, надо последовательно раскрывать каждый символ в
соответствии
с операциями и теми предшествующими символами,
которые используются для получения данного символа. Продвижение по
схеме прекращается, когда в формулу будут подставлены только входные
переменные. Эту формулу можно затем упростить и по ней построить
новую, более простую схему.
Пример. Дана схема, для которой нужно записать формулу, упростить
ее и построить новую схему.
A B C x1 x 2 x 3 ( x1 x 2 x 3 );
Теперь упростим эту формулу:
A B C x1 x2 x3 ( x1 x2 x3 ) ( x1 x2 x3 )( x1 x2 x3 )
( x1 x2 x3 ) ( x1 x2 x3 ) x1 x2 x3 x1 x2 x3 x1 x2 .
Последней конъюнкции соответствует следующая схема: