1_Algebra_logiki
.pdf
Функции алгебры логики Формульное представление булевой функции
Формульное представление булевой функции
Формула над 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 = x1 _ f1(x1; x2)
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
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 = x1 _ f1(x1; x2) = f2 x1; f1(x1; x2)
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
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 = x1 _ f1(x1; x2) = f2 x1; f1(x1; x2)
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 = x1 _ f1(x1; x2) = f2 x1; f1(x1; x2)
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 = x1 _ f1(x1; x2) = f2 x1; f1(x1; x2)
x1_ (x1x2) = x1 _ f3( 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 = x1 _ f1(x1; x2) = f2 x1; f1(x1; x2)
x1_ (x1x2) = x1 _ f3( 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 = x1 _ f1(x1; x2) = f2 x1; f1(x1; x2)
x1_ (x1x2) = x1 _ f3( x1x2 ) = f2 x1; f3 f1(x1; x2)
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
6 / 50 |
Функции алгебры логики |
Формульное представление булевой функции |
Формульное представление булевой функции
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
7 / 50 |
Функции алгебры логики |
Формульное представление булевой функции |
Формульное представление булевой функции
A ( x1; x2; : : : ; xn )
Указаны переменные x1; x2; : : : ; xn, участвующие в построении формулы
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
7 / 50 |
|
Функции алгебры логики |
Формульное представление булевой функции |
|
Формульное представление булевой функции |
|
||
A ( x1; x2; : : : ; xn ) |
|
A [ f1; f2; : : : ; fm ] |
|
Указаны |
переменные |
Указаны |
функции |
x1; x2; : : : ; xn, участвующие в |
f1; f2; : : : ; fm, используемые для |
||
построении формулы |
|
построения формулы |
|
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
7 / 50 |