1_Algebra_logiki
.pdf
Функции алгебры логики |
Формульное представление булевой функции |
Формульное представление булевой функции
Формула над D
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
6 / 50 |
Функции алгебры логики |
Формульное представление булевой функции |
Формульное представление булевой функции
Формула над D
D = ff1; : : : ; fk; : : : g, 8fi 2 P2.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
6 / 50 |
Функции алгебры логики |
Формульное представление булевой функции |
Формульное представление булевой функции
Формула над D
D = ff1; : : : ; fk; : : : g, 8fi 2 P2.
Базис индукции. Выражение fi(x1; : : : ; xn), ãäå fi 2 D, формула над D.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
6 / 50 |
Функции алгебры логики Формульное представление булевой функции
Формульное представление булевой функции
Формула над D
D = ff1; : : : ; fk; : : : g, 8fi 2 P2.
Базис индукции. Выражение fi(x1; : : : ; xn), ãäå fi 2 D, формула над D.
Индуктивный переход. Пусть fj(x1; : : : ; xn) 2 D è A1; : : : ; An выражения, являющиеся либо формулами над D, либо символами
переменных.
Тогда выражение fj(A1; : : : ; An) формула над D.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
6 / 50 |
Функции алгебры логики Формульное представление булевой функции
Формульное представление булевой функции
Формула над D
D = ff1; : : : ; fk; : : : g, 8fi 2 P2.
Базис индукции. Выражение fi(x1; : : : ; xn), ãäå fi 2 D, формула над D.
Индуктивный переход. Пусть fj(x1; : : : ; xn) 2 D |
è A1; : : : ; An |
|||||||||
выражения, |
|
являющиеся либо формулами над D, |
либо символами |
|||||||
переменных. |
|
|
|
|
|
|
|
|||
Тогда выражение fj(A1; : : : ; An) формула над D. |
|
|||||||||
D = fx1 ^ x2; x1 _ x2; x1 g |
|
|||||||||
| |
|
{zf1 |
|
} |
| |
|
{zf2 |
|
} |{z}f3 |
|
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
6 / 50 |
Функции алгебры логики Формульное представление булевой функции
Формульное представление булевой функции
Формула над D
D = ff1; : : : ; fk; : : : g, 8fi 2 P2.
Базис индукции. Выражение fi(x1; : : : ; xn), ãäå fi 2 D, формула над D.
Индуктивный |
переход. Пусть fj(x1; : : : ; xn) 2 D |
è A1; : : : ; An |
|||||||||
выражения, |
являющиеся либо формулами над D, |
либо символами |
|||||||||
переменных. |
|
|
|
|
|
|
|
||||
Тогда выражение fj(A1; : : : ; An) формула над D. |
|
||||||||||
D = fx1 ^ x2; x1 _ x2; x1 g |
|
||||||||||
| |
|
{z |
|
} |
| |
|
{z |
|
} |
|{z} |
|
|
|
f1 |
|
|
f2 |
f3 |
|
||||
Формулы над D:
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
6 / 50 |
Функции алгебры логики Формульное представление булевой функции
Формульное представление булевой функции
Формула над D
D = ff1; : : : ; fk; : : : g, 8fi 2 P2.
Базис индукции. Выражение fi(x1; : : : ; xn), ãäå fi 2 D, формула над D.
Индуктивный |
переход. Пусть fj(x1; : : : ; xn) 2 D |
è A1; : : : ; An |
|||||||||
выражения, |
являющиеся либо формулами над D, |
либо символами |
|||||||||
переменных. |
|
|
|
|
|
|
|
||||
Тогда выражение fj(A1; : : : ; An) формула над D. |
|
||||||||||
D = fx1 ^ x2; x1 _ x2; x1 g |
|
||||||||||
| |
|
{z |
|
} |
| |
|
{z |
|
} |
|{z} |
|
|
|
f1 |
|
|
f2 |
f3 |
|
||||
Формулы над D:
y _ x4
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
6 / 50 |
Функции алгебры логики Формульное представление булевой функции
Формульное представление булевой функции
Формула над D
D = ff1; : : : ; fk; : : : g, 8fi 2 P2.
Базис индукции. Выражение fi(x1; : : : ; xn), ãäå fi 2 D, формула над D.
Индуктивный |
переход. Пусть fj(x1; : : : ; xn) 2 D |
è A1; : : : ; An |
|||||||||
выражения, |
являющиеся либо формулами над D, |
либо символами |
|||||||||
переменных. |
|
|
|
|
|
|
|
||||
Тогда выражение fj(A1; : : : ; An) формула над D. |
|
||||||||||
D = fx1 ^ x2; x1 _ x2; x1 g |
|
||||||||||
| |
|
{z |
|
} |
| |
|
{z |
|
} |
|{z} |
|
|
|
f1 |
|
|
f2 |
f3 |
|
||||
Формулы над D:
y _ x4 = f2(y; x4)
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
6 / 50 |
Функции алгебры логики Формульное представление булевой функции
Формульное представление булевой функции
Формула над D
D = ff1; : : : ; fk; : : : g, 8fi 2 P2.
Базис индукции. Выражение fi(x1; : : : ; xn), ãäå fi 2 D, формула над D.
Индуктивный |
переход. Пусть fj(x1; : : : ; xn) 2 D |
è A1; : : : ; An |
|||||||||
выражения, |
являющиеся либо формулами над D, |
либо символами |
|||||||||
переменных. |
|
|
|
|
|
|
|
||||
Тогда выражение fj(A1; : : : ; An) формула над D. |
|
||||||||||
D = fx1 ^ x2; x1 _ x2; x1 g |
|
||||||||||
| |
|
{z |
|
} |
| |
|
{z |
|
} |
|{z} |
|
|
|
f1 |
|
|
f2 |
f3 |
|
||||
Формулы над D:
y _ x4 = f2(y; x4) 
x1_ x1x2
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
6 / 50 |
Функции алгебры логики Формульное представление булевой функции
Формульное представление булевой функции
Формула над D
D = ff1; : : : ; fk; : : : g, 8fi 2 P2.
Базис индукции. Выражение fi(x1; : : : ; xn), ãäå fi 2 D, формула над D.
Индуктивный |
переход. Пусть fj(x1; : : : ; xn) 2 D |
è A1; : : : ; An |
|||||||||
выражения, |
являющиеся либо формулами над D, |
либо символами |
|||||||||
переменных. |
|
|
|
|
|
|
|
||||
Тогда выражение fj(A1; : : : ; An) формула над D. |
|
||||||||||
D = fx1 ^ x2; x1 _ x2; x1 g |
|
||||||||||
| |
|
{z |
|
} |
| |
|
{z |
|
} |
|{z} |
|
|
|
f1 |
|
|
f2 |
f3 |
|
||||
Формулы над D:
y _ x4 = f2(y; x4) 
x1_ x1x2
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
6 / 50 |