1_Algebra_logiki
.pdf
Полнота и замкнутость |
Теорема I о полноте |
Теорема I о полноте систем булевых функций
Пример
Пример
M = f_; ^; xg è N = f_; xg
x ^ y = x _ y.
Пример
M = f_; ^; xg è N = f^; xg
x _ y = x ^ y.
Пример
M = f_; ^; xg è
N = f"g (x " y = x ^ y)
x ^ y = x " y
x = x ^ x = x " x
x ^ y = x ^ y = x " y = (x " y) " (x " y)
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
31 / 50 |
Полнота и замкнутость |
Теорема I о полноте |
Теорема I о полноте систем булевых функций
Пример
Пример
M = f_; ^; xg è N = f_; xg
x ^ y = x _ y.
Пример
M = f_; ^; xg è N = f^; xg
x _ y = x ^ y.
Пример
M = f_; ^; xg è
N = f"g (x " y = x ^ y)
x ^ y = x " y
x = x ^ x = x " x
x ^ y = x ^ y = x " y = (x " y) " (x " y)
x _ y = x ^ y = x " y = (x " x) " (y " y)
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
31 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Замкнутые классы
Замыкание
Замыканием над системой
M = ff1; : : : ; fr; : : : g ([M])
называется множество всех булевых функций, представимых формулами над M.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
32 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Замкнутые классы
Замыкание
Замыканием над системой
M = ff1; : : : ; fr; : : : g ([M])
называется множество всех булевых функций, представимых формулами над M.
[M] обязательно содержит M.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
32 / 50 |
|
Полнота и замкнутость |
Замкнутые классы |
|
Замкнутые классы |
|
|
|
Замыкание |
|
|
Cвойства замыкания: |
Замыканием |
íàä |
системой |
|
M = ff1; : : : ; fr; : : : g ([M])
называется множество всех булевых функций, представимых формулами над M.
[M] обязательно содержит M.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
32 / 50 |
|
Полнота и замкнутость |
Замкнутые классы |
||
Замкнутые классы |
|
|
|
|
Замыкание |
|
|
Cвойства замыкания: |
|
Замыканием |
íàä |
системой |
1 |
[M] = [M]. |
M = ff1; : : : ; fr; : : : g ([M])
называется множество всех булевых функций, представимых формулами над M.
[M] обязательно содержит M.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
32 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Замкнутые классы
Замыкание
Замыканием над системой
M = ff1; : : : ; fr; : : : g ([M])
называется множество всех булевых функций, представимых формулами над M.
[M] обязательно содержит M.
Cвойства замыкания:
1[M] = [M].
2 [P2] = P2.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
32 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Замкнутые классы
Замыкание
Замыканием над системой
M = ff1; : : : ; fr; : : : g ([M])
называется множество всех булевых функций, представимых формулами над M.
[M] обязательно содержит M.
Cвойства замыкания:
1[M] = [M].
2 [P2] = P2.
3 Åñëè M N, òî [M] [N].
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
32 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Замкнутые классы
Замыкание
Замыканием над системой
M = ff1; : : : ; fr; : : : g ([M])
называется множество всех булевых функций, представимых формулами над M.
[M] обязательно содержит M.
Cвойства замыкания:
1[M] = [M].
2 [P2] = P2.
3 Åñëè M N, òî [M] [N].
4 [M] [ [N] [M [ N].
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
32 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Замкнутые классы
Замыкание
Замыканием над системой
M = ff1; : : : ; fr; : : : g ([M])
называется множество всех булевых функций, представимых формулами над M.
[M] обязательно содержит M.
Замкнутый класс
Cвойства замыкания:
1[M] = [M].
2 [P2] = P2.
3 Åñëè M N, òî [M] [N].
4 [M] [ [N] [M [ N].
Класс M называется замкнутым если [M] = M.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
32 / 50 |