1_Algebra_logiki
.pdfПолнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
Лемма о несамодвойственной функции
Если функция f(x1; : : : ; xn) 2= S, то из нее путем замены переменных на x или x можно получить несамодвойственную функцию одной переменной, то есть константу.
Доказательство
f 2= S ) существует такой набор значений переменных
( 1; : : : ; n), ÷òî f( 1; : : : ; n) = f( 1; : : : ; n) '(x) = f(x 1 ; : : : ; x i; : : : ; x n)
'(x) получена из f(x1; : : : ; xn) заменой ее аргументов на x или x.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
36 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
Лемма о несамодвойственной функции
Если функция f(x1; : : : ; xn) 2= S, то из нее путем замены переменных на x или x можно получить несамодвойственную функцию одной переменной, то есть константу.
Доказательство
f 2= S ) существует такой набор значений переменных
( 1; : : : ; n), ÷òî f( 1; : : : ; n) = f( 1; : : : ; n) '(x) = f(x 1 ; : : : ; x i; : : : ; x n)
'(x) получена из f(x1; : : : ; xn) заменой ее аргументов на x или x. ) '(x) соответствует условиям леммы
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
36 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
Лемма о несамодвойственной функции
Если функция f(x1; : : : ; xn) 2= S, то из нее путем замены переменных на x или x можно получить несамодвойственную функцию одной переменной, то есть константу.
Доказательство
f 2= S ) существует такой набор значений переменных
( 1; : : : ; n), ÷òî f( 1; : : : ; n) = f( 1; : : : ; n) '(x) = f(x 1 ; : : : ; x i; : : : ; x n)
'(x) получена из f(x1; : : : ; xn) заменой ее аргументов на x или x. ) '(x) соответствует условиям леммы
'(0)
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
36 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
Лемма о несамодвойственной функции
Если функция f(x1; : : : ; xn) 2= S, то из нее путем замены переменных на x или x можно получить несамодвойственную функцию одной переменной, то есть константу.
Доказательство
f 2= S ) существует такой набор значений переменных
( 1; : : : ; n), ÷òî f( 1; : : : ; n) = f( 1; : : : ; n) '(x) = f(x 1 ; : : : ; x i; : : : ; x n)
'(x) получена из f(x1; : : : ; xn) заменой ее аргументов на x или x. ) '(x) соответствует условиям леммы
'(0) =f(0 1 ; : : : ; 0 n ) =
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
36 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
Лемма о несамодвойственной функции
Если функция f(x1; : : : ; xn) 2= S, то из нее путем замены переменных на x или x можно получить несамодвойственную функцию одной переменной, то есть константу.
Доказательство
f 2= S ) существует такой набор значений переменных
( 1; : : : ; n), ÷òî f( 1; : : : ; n) = f( 1; : : : ; n) '(x) = f(x 1 ; : : : ; x i; : : : ; x n)
'(x) получена из f(x1; : : : ; xn) заменой ее аргументов на x или x. ) '(x) соответствует условиям леммы
'(0) =f(0 1 ; : : : ; 0 n ) =
0 i = i
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
36 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
Лемма о несамодвойственной функции
Если функция f(x1; : : : ; xn) 2= S, то из нее путем замены переменных на x или x можно получить несамодвойственную функцию одной переменной, то есть константу.
Доказательство
f 2= S ) существует такой набор значений переменных
( 1; : : : ; n), ÷òî f( 1; : : : ; n) = f( 1; : : : ; n) '(x) = f(x 1 ; : : : ; x i; : : : ; x n)
'(x) получена из f(x1; : : : ; xn) заменой ее аргументов на x или x. ) '(x) соответствует условиям леммы
'(0) =f(0 1 ; : : : ; 0 n ) =
f( 1; : : : ; n) = f( 1; : : : ; n) =
0 i = i
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
36 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
Лемма о несамодвойственной функции
Если функция f(x1; : : : ; xn) 2= S, то из нее путем замены переменных на x или x можно получить несамодвойственную функцию одной переменной, то есть константу.
Доказательство
f 2= S ) существует такой набор значений переменных
( 1; : : : ; n), ÷òî f( 1; : : : ; n) = f( 1; : : : ; n) '(x) = f(x 1 ; : : : ; x i; : : : ; x n)
'(x) получена из f(x1; : : : ; xn) заменой ее аргументов на x или x. ) '(x) соответствует условиям леммы
'(0) =f(0 1 ; : : : ; 0 n ) =
f( 1; : : : ; n) = f( 1; : : : ; n) =
0 i = i
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
36 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
Лемма о несамодвойственной функции
Если функция f(x1; : : : ; xn) 2= S, то из нее путем замены переменных на x или x можно получить несамодвойственную функцию одной переменной, то есть константу.
Доказательство
f 2= S ) существует такой набор значений переменных
( 1; : : : ; n), ÷òî f( 1; : : : ; n) = f( 1; : : : ; n) '(x) = f(x 1 ; : : : ; x i; : : : ; x n)
'(x) получена из f(x1; : : : ; xn) заменой ее аргументов на x или x. ) '(x) соответствует условиям леммы
'(0) =f(0 1 ; : : : ; 0 n ) =
f( 1; : : : ; n) = f( 1; : : : ; n) =
0 i = i
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
36 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
Лемма о несамодвойственной функции
Если функция f(x1; : : : ; xn) 2= S, то из нее путем замены переменных на x или x можно получить несамодвойственную функцию одной переменной, то есть константу.
Доказательство
f 2= S ) существует такой набор значений переменных
( 1; : : : ; n), ÷òî f( 1; : : : ; n) = f( 1; : : : ; n) '(x) = f(x 1 ; : : : ; x i; : : : ; x n)
'(x) получена из f(x1; : : : ; xn) заменой ее аргументов на x или x. ) '(x) соответствует условиям леммы
'(0) =f(0 1 ; : : : ; 0 n ) =
f( 1; : : : ; n) = f( 1; : : : ; n) =
1 i= i
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
36 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
Лемма о несамодвойственной функции
Если функция f(x1; : : : ; xn) 2= S, то из нее путем замены переменных на x или x можно получить несамодвойственную функцию одной переменной, то есть константу.
Доказательство
f 2= S ) существует такой набор значений переменных
( 1; : : : ; n), ÷òî f( 1; : : : ; n) = f( 1; : : : ; n) '(x) = f(x 1 ; : : : ; x i; : : : ; x n)
'(x) получена из f(x1; : : : ; xn) заменой ее аргументов на x или x. ) '(x) соответствует условиям леммы
'(0) =f(0 1 ; : : : ; 0 n ) =
f( 1; : : : ; n) = f( 1; : : : ; n) = f(1 1 ; : : : ; 1 n )
1 i= i
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
36 / 50 |