1_Algebra_logiki
.pdf
Функции алгебры логики |
Формульное представление булевой функции |
Порядок выполнения операций в формулах
A = x _ y x z
|{z}
|
{z
}
1;2 3
| {z }
4
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
8 / 50 |
Функции алгебры логики |
Формульное представление булевой функции |
Порядок выполнения операций в формулах
A = x _ y x z
|{z}
|
{z
}
1;2 3
| {z }
4
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
8 / 50 |
Функции алгебры логики |
Формульное представление булевой функции |
Порядок выполнения операций в формулах
|
|
|
|
|
|
|
|
|
x y z |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 0 0 |
|
|
|
|
|
|
|
|
|
0 0 1 |
|
|
|
|
|
|
|
|
||
A = x _ y x z |
0 1 0 |
||||||||
1;2 |
4 |
|
|{z} |
0 1 1 |
|||||
|
| {z } |
3 |
|
1 0 0 |
|||||
| |
|
|
{z |
|
|
} |
|
||
|
|
|
|
1 0 1 |
|||||
|
|
|
|
|
|
|
|
|
1 1 0 |
|
|
|
|
|
|
|
|
|
1 1 1 |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
8 / 50 |
Функции алгебры логики |
Формульное представление булевой функции |
Порядок выполнения операций в формулах
|
|
|
|
|
|
|
|
x y z |
|
x _ y |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 0 0 |
1 |
|
|
|
|
|
|
|
|
|
|
0 0 1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A = x _ y x z |
0 1 0 |
0 |
|
||||||||
1;2 |
|
|
|
|{z} |
|
0 1 1 |
0 |
|
|||
|
|
|
|
4 |
|
1 0 0 |
0 |
|
|||
|
| {z } |
3 |
|
|
|||||||
| |
|
{z |
} |
|
|
|
|||||
|
1 0 1 |
0 |
|
||||||||
|
|
|
|
|
|
|
|
1 1 0 |
0 |
|
|
|
|
|
|
|
|
|
|
1 1 1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
8 / 50 |
Функции алгебры логики |
Формульное представление булевой функции |
Порядок выполнения операций в формулах
|
|
|
|
|
|
|
|
x y z |
|
x _ y |
|
x z |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 0 0 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
0 0 1 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A = x _ y x z |
0 1 0 |
0 |
|
0 |
||||||||
1;2 |
|
|
|
|{z} |
|
0 1 1 |
0 |
|
0 |
|||
|
|
|
|
4 |
|
1 0 0 |
0 |
|
0 |
|||
|
| {z } |
3 |
|
|
||||||||
| |
|
{z |
} |
|
|
|
|
|||||
|
1 0 1 |
0 |
|
1 |
||||||||
|
|
|
|
|
|
|
|
1 1 0 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
1 1 1 |
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
8 / 50 |
Функции алгебры логики |
Формульное представление булевой функции |
Порядок выполнения операций в формулах
|
|
|
|
|
|
|
|
x y z |
|
x _ y |
|
x z |
A |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 0 0 |
1 |
|
0 |
1 |
|
|
|
|
|
|
|
|
|
0 0 1 |
1 |
|
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A = x _ y x z |
0 1 0 |
0 |
|
0 |
0 |
||||||||
1;2 |
|
|
|
|{z} |
|
0 1 1 |
0 |
|
0 |
0 |
|||
|
|
|
|
4 |
|
1 0 0 |
0 |
|
0 |
0 |
|||
|
| {z } |
3 |
|
|
|||||||||
| |
|
{z |
} |
|
|
|
|
|
|||||
|
1 0 1 |
0 |
|
1 |
1 |
||||||||
|
|
|
|
|
|
|
|
1 1 0 |
0 |
|
0 |
0 |
|
|
|
|
|
|
|
|
|
1 1 1 |
0 |
|
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
8 / 50 |
Функции алгебры логики |
Формульное представление булевой функции |
Порядок выполнения операций в формулах
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x y z |
|
x _ y |
|
x z |
A |
x _ y x z |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
0 0 0 |
1 |
|
0 |
1 |
|
0 _ 0 0 0 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
0 0 1 |
1 |
|
0 |
1 |
|
0 _ 0 0 1 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
A = x _ y x z |
0 1 0 |
0 |
|
0 |
0 |
|
0 _ 1 0 0 |
||||||||||||
|
|
|
|{z} |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
||
1;2 |
|
|
|
|
|
|
|
|
|
0 |
_ |
1 |
0 |
||||||
|
|
|
4 |
|
1 0 0 |
0 |
|
0 |
0 |
1 |
|
0 |
|
1 |
0 |
||||
|
| {z } |
3 |
|
0 1 1 |
0 |
|
0 |
0 |
|
|
|||||||||
| |
|
{z |
} |
|
|
|
|
|
|
_ |
|
|
|
|
|||||
|
1 0 1 |
0 |
|
1 |
1 |
|
|
|
|
|
1 |
1 |
|||||||
|
|
1 |
_ |
0 |
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
1 1 0 |
0 |
|
0 |
0 |
|
1 _ 1 1 0 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
1 1 1 |
0 |
|
1 |
1 |
|
1 _ 1 1 1 |
||||||
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
8 / 50 |
Функции алгебры логики Существенные и фиктивные переменные
Существенные и фиктивные переменные
Cущественная переменная
Булева функция f(x1; : : : ; xi 1; xi; xi+1; : : : ; xn) 2 P2 зависит существенным образом от аргумента xi, если существуют такие значения
1; : : : ; i 1; i+1; : : : ; n переменных x1; : : : ; xi 1; xi+1; : : : ; xn, ÷òî
f( 1; : : : ; i 1; 0; i+1; : : : ; n) 6= f( 1; : : : ; i 1; 1; i+1; : : : ; n):
В этом случае переменная xi называется существенной, иначе несущественной или фиктивной.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
9 / 50 |
Функции алгебры логики Существенные и фиктивные переменные
Существенные и фиктивные переменные
Cущественная переменная
Булева функция f(x1; : : : ; xi 1; xi; xi+1; : : : ; xn) 2 P2 зависит существенным образом от аргумента xi, если существуют такие значения
1; : : : ; i 1; i+1; : : : ; n переменных x1; : : : ; xi 1; xi+1; : : : ; xn, ÷òî
f( 1; : : : ; i 1; 0; i+1; : : : ; n) 6= f( 1; : : : ; i 1; 1; i+1; : : : ; n):
В этом случае переменная xi несущественной или фиктивной.
Пример |
|
|
|
|
|
|
|
x1 x2 |
|
f |
|
|
|
|
|
|
|
|
||
|
0 0 |
|
1 |
|
x1 |
f |
|
0 1 |
|
1 |
() |
0 |
1 |
1 0 |
|
0 |
|
1 |
0 |
|
|
|
|
|
|
|
|
1 1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
называется существенной, иначе
x1 |
|
существенная |
переменная для f(x1; x2) |
||
x2 |
|
несущественная |
(фиктивная) |
переменная |
|
äëÿ f(x1; x2) |
|
|
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
9 / 50 |
Функции алгебры логики |
Существенные и фиктивные переменные |
|
||
Существенные и фиктивные переменные |
|
|
||
Cущественная переменная |
|
|
|
|
Булева функция f(x1; : : : ; xi 1; xi; xi+1; : : : ; xn) |
2 |
P2 |
зависит |
|
существенным образом от аргумента |
xi, если существуют такие значения |
|||
1; : : : ; i 1; i+1; : : : ; n переменных x1; : : : ; xi 1; xi+1; : : : ; xn, ÷òî |
|
|||
f( 1; : : : ; i 1; 0; i+1; : : : ; n) 6= f( 1; : : : ; i 1; 1; i+1; : : : ; n): |
||||
В этом случае переменная xi |
называется |
существенной, |
иначе |
|
несущественной или фиктивной. |
|
|
|
|
Равные функции
Две булевы функции f и g называются равными, если одну из них можно получить из другой, добавляя или исключая фиктивные переменные.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
9 / 50 |