Элементы алгебры логики

1. Элементы алгебры логики

Саровский физико-технический институт
Национального исследовательского ядерного университета МИФИ
Элементы алгебры логики
Алексеев В.В.
Саров
2016
1

2. Понятие цифрового автомата

• цифровым автоматом называется
устройство, предназначенное для
преобразования цифровой (дискретной)
информации, способное переходить под
воздействием входных сигналов из одного
состояния в другие и выдавать выходные
сигналы.
• Отличительные особенности ЦА
заключаются в том, что они имеют
дискретное множество внутренних
состояний и переход из одного в другое
осуществляется скачкообразно.
2

3. различают автоматы синхронного и асинхронного действия.

•различают автоматы синхронного и
асинхронного действия.
• Для идеализированных ЦА не
учитывается переходные процессы в
схемах и разница в фактических
величинах Т для правильного
функционирования не имеет значение.
• По степени детализации описания ЦА
различают автоматы абстрактные и
структурные. В соответствии с этим
различают абстрактную и структурную
теорию ЦА.
3

4.

• Абстрактные ЦА рассматриваются как "
черный ящик ", имеющий один вход и
один выход, т. е. отвлекаются от
структуры ЦА и его входных Х (t) и
выходных Y (t) сигналов.
X x0 , x1 , x2 , xm
- входной
- выходной Y y0 , y1 , y2 , yn
S
s
,
s
,
s
,
s
0
1
2
k
- состояний
4

5. Тогда закон функционирования абстрактного автомата может быть задан уравнениями:

S (t 1) f [s(t ),x(t )];
Y (t ) p[x(t ),s(t )];
(1)
S ( 0) s 0 ;
- где (s, x) - функция переходов
автомата ;
p (x, s) - функция выходов автомата ;
s0- начальное состояние автомата .
(Автомат Мили)
5

6.

• ЦА, выходные сигналы в которых зависят
только от состояния автомата и не
зависят от значения входных сигналов,
называются автоматами Мура
X ( t 1) f [ s ( t ), x ( t ) ];
(2)
Y ( t ) [ s ( t ) ];
S ( 0) s0 ;
где [ s (t) ] -сдвинутая функция выхода.
6

7.

• ЦА, имеющая более одного внутреннего
состояния, называются автоматами с
памятью. Частный случай абстрактных
ЦА - автоматы с одним внутренним
состоянием. Такие тривиальные автоматы
называют автоматами без памяти или
комбинационными схемами. Закон
функционирования таких автоматов будет
определяться одним уравнением:
Y (t) = [ x(t)]
7

8. Функции алгебры логики и их основные свойства.

Основные определения
1. Основное понятие АЛ - высказывание.
Высказывание - некоторое предложение,
о котором можно утверждать, что оно
истинно или ложно.
2. Логическая (Булева) переменная такая величина X, которая может
принимать только два значения:
X = { 0, 1 }.
8

9.

3. Логическая функция ( функция
алгебры логики - ФАЛ ) - функция
(x 1 , x 2 ,....x n ) , принимающая значение,
равное нулю или единице на наборе
логических переменных x 1 , x 2 ,....x n .
Пусть X x1 , x2 , xn | xi Y и Y 0, 1
4. Функцией алгебры логики (ФАЛ)
называется функция, дающая
однозначное отображение X в Y, т.е.
f ( x1 , x2 , xn ) : X Y
9

10.

• 5. Если две ФАЛ f1 ( x1 x2 xn )и f 2 ( x1 x2 xn )
принимают на всех возможных наборах
значений аргументов одинаковые значения,
то функции 1 и 2 называются
равносильными (равными), т.е.:
f1 ( x1 x2 xn )= f 2 ( x1 x2 xn )
6. Функция f ( x1 xi 1 , xi ,xi 1 xn ) существенно
зависит от аргумента , если имеет место
соотношение:
f ( x1 , xi 1 ,0, xi 1 , xn ) f ( x1 , xi 1 ,1, xi 1 , xn )
10

11.

7. ФАЛ называют не полностью
определенными или недоопределенными, если на некоторых
наборах значения ФАЛ не определены.
• Если ФАЛ не определена на m наборах
аргументов, то путем ее произвольного
доопределения можно получить 2m
различных полностью определенных
функций.
11

12. Теорема:

Число различных ФАЛ, зависящих
от
n
2n
аргументов конечно и равно 2 .
12

13. Теорема:

• Число ФАЛ, существенно зависящих от n
аргументов, определяется следующим
рекуррентным соотношением:
2n
An 2 C
n 1
n
An 1 C
n 2
n
An 2 C A1 A0
1
n
где Аi - число ФАЛ, существенно зависящих
от i аргументов,
n!
C
k!(n k )!
k
n
13

14.

• Правая часть соотношения есть разность
между числом всех ФАЛ и суммой всех
ФАЛ, существенно зависящих от любого
числа аргументов, меньших чем n.
• Вместо рекуррентного соотношения
можно найти прямое выражение для
значений:
m
A m ( 1) C k 2
k
2 m k
k 0
14

15. Пример:

• Найти число ФАЛ, существенно
зависящих от 3-х переменных.
20
1
Имеем: A0 2 2 2.
A1 2
A2 2
A3 2
23
22
21
A0 4 2 2
2!
1
4
C2 A1 A 0 2
2 2 10
1!1!
C 23 A 2 C13 A 1 A 0 256 30 6 2 218
15

16. Элементарные функции алгебры логики

• n=1. Число ФАЛ равно 4:
f1 ( x) 0;
f 2 ( x) 1;
f 3 ( x) x;
f 4 ( x) x.
16

17. Элементарные ФАЛ 2-х переменных

• n=2; Число ФАЛ равно 16.
17

18.

• имеем 10 различных функций, существенно
зависящих от аргументов x1 и x2 .
18

19. 1.

f ( x1 , x2 ) x1 x2 x1 & x2 x1 x2
• конъюнкция (логическое умножение,
или функция И) истинна тогда и только
тогда, когда и x1 и x2 истинны.
19

20. 2.

f ( x1 , x2 ) x1 x2
• дизъюнкция (логическое сложение,
или функция ИЛИ) истинна тогда, и
только тогда, когда истинны или x1, или
x2, или обе переменные.
20

21. 3.

f ( x1 , x2 ) x1 x2
• Функция сложения по модулю 2 (или
функция разноименности, или
функция исключающее ИЛИ) истинна
тогда и только тогда когда x1 x2.
21

22. 4.

f ( x1 , x2 ) x1 x2 x1 ~ x2
• функция равнозначности, которая
истинна тогда и только тогда, когда обе
переменные или истинны, или ложны.
22

23. 5.

f ( x1 , x2 ) x1 x2
• импликация х1 в х2 ложна тогда и
только тогда, когда х1 истинна, а х2
ложна
23

24. 6.

f x1 x 2
• функция Пирса ( Вебба ) истинна тогда
и только тогда, когда х1 и х2 ложны.
24

25. 7.

f ( x1 , x2 ) x1 / x2
• Функция Шеффера ложна только тогда и
только тогда, когда х1и х2 истинны.
25

26.

26

27. Выражение одних элементарных функций через другие.

1. x1
x2 x1 x2 ;
27

28. 2.

x1 x2 x1 ~ x2
3. x1 ~ x2 ( x1 x2 ) ( x1 x 2 ) ( x1 x2 ) ( x2 x1 )
28

29.

4.
x1 x2 x1 x 2
5. x1
x 2 x1 x 2
29

30. Свойства элементарных ФАЛ.

x x;
x x x;
x x x;
x x 1;
x x 0;
x 1 1;
x 0 x;
x 1 x;
x 0 0.
30

31. Свойства конъюнкции, дизъюнкции, отрицания

1. Свойство ассоциативности
(сочетательный закон):
x1 ( x2 x3 ) ( x1 x2 ) x3 ( x1 x3 ) x2
x1 (x 2 x 3 ) (x1 x 2 ) x 3 (x1 x 3 ) x 2
2. Свойство коммутативности
(переместительный закон):
1
2
2
1; 1
2
x x x x
x x x2 x1
31

32.

3. Свойство дистрибутивности
(распределительный закон):
• для конъюнкции относительно дизъюнкции:
x1 & (x 2 x 3 ) (x1 & x 2 ) (x1 & x 3 )
• для дизъюнкции относительно конъюнкции:
x1 x 2 & x 3 (x1 x 2 ) & (x1 x 3 )
Действительно:
32

33.

( x1 x2 ) ( x1 x3 )
x1 x1 x1 x3 x2 x1 x2 x3
x1 x1 x3 x1 x2 x2 x3
x1 (1 x3 x2 ) x2 x3 x1 x2 x3
33

34. Законы Де-Моргана:

1.
x1 x2 x3 xn
x1 & x2 & x3 & & x n
2.
x1 & x2 & x3 & & xn
x1 x2 x3 xn
34

35. Законы (правила) поглощения:

1.
x1 x1 x 2 x1
2.
x1 (x1 x 2 ) x1
x 1 x 1 x 2 x 1 (1 x 2 ) x 1 1 x 1
x1 ( x1 x2 ) x1 x1 x1 x2
x1 x1 x2 x1 (1 x2 ) x1
35

36. Из логических функций устанавливается

• правило склеивания:
x1x 2 x1x 2 x1
• правило вычеркивания:
x1 x1 x 2 x1 x 2
36

37.

x1 x1 x2 x1 1 x1 x2
x1 ( x2 x2 ) x1 x2
x1 x2 x1 x2 x1 x2
(x1 x2 x1 x2 ) ( x1 x2 x1 x2 )
x1 ( x2 x2 ) x2 ( x1 x1 )
x1 1 x2 1 x1 x2 .
37

38.

• Знание свойств, законов и
правил элементарных ФАЛ
необходимо для аналитического
описания функций алгебры
логики, их преобразований.
38

39. Свойства функции сложения по модулю два

x1 x2 x1 x2 ( x1 x2 ) ( x1 x2 )
( x1 x2 ) ( x1 x2 )
x1 x2 x1 x2 ( x1 x2 ) ( x1 x2 )
Функция сложения по модулю два
обладает следующими свойствами:
коммутативности (переместительный
закон)
1
2
2
1
x x x x
39

40.

ассоциативности (сочетательный закон):
x1 (x 2 x 3 ) (x1 x 2 ) x 3
дистрибутивности (распределительный
закон):
x1 (x 2 x 3 ) x1 x 2 x1 x 3
справедливы правила:
x x 0
x x 1
x 0 x
x 1 x
40

41.

• Функции НЕ, ИЛИ, НЕ могут быть
выражены через функцию сложения по
модулю два следующим образом:
x x 1
x1 x 2 x1 x 2 x1 x 2
x1 x 2 (x1 x 2 ) (x1 x 2 )
41

42. Свойства функции импликации

x1 x 2 x1 x 2
• Для функции импликации справедливы
следующие правила:
• x x 1
x 0 x
x x x
x 1 1
0 x 1
1 x x
42

43.

x1 x 2 x 2 x1
• Функции НЕ, ИЛИ, И выражаются через
импликацию следующим образом:
x x 0
x 1 x 2 x 1 x 2 ( x 1 0) x 2
x1 x2 x1 x2 x1 ( x2 0)
[ x1 ( x2 0)]
43

44.

44