Лемма о немонотонных функциях.

Если система функций содержит немонотонную функцию, то подстановкой констант можно получить отрицание, то есть существует такая подстановка n-1 константы, что получится функция одной переменной, реализующая отрицание.

Существует сигма и тау такие что сигма>тау

f(сигма)>f(тау).

Это возможно, когда f(сигма)=1, а f(тау)=0

Если наборы сигма и тау отл к комп., то в этих к компонетах а наборе сигма стоят 1, а в наборе тау – 0.

Если взять набор сигма и заменить поочередно в этих к комп. 0 и 1, то пол последовательность омега.

d<w₁<w₂<…<w_k-1<t

Любые 2 набора стоящие радом отличаются только в одном комп., то есть я вл. соседними; очевидно, что в такой цепочке найдуться 2 набора w_j и w_j+1 такие что f(w_j)=1 f(w_j+1)=0, так как они отлиаются только в одном комп., то их можно рассматривать как функции одной переменной и получить следующее:

f(0)=1; f(1)=0 из немонотонной функции путем подстановки констант можно получить отрицание.

Лемма о нелинейных функциях.

Если f(x1, x2, …, xn) – нелинейная функция, то с помощью подстановок констант и использования отрицания из нее можно получить конъюнкцию и дизъюнкцию.

Рассмотрим функцию f(x1, x2, …, xn) – нелин.: значит ее полином Жегалкина содержит конъюнкцию нескольких переменных. Рассмотрим самую короткую из конъюнкций:

k=x₁x₂…x_k

Пусть x₃…x_k=1, тогда k=x₁x₂

Вместо x₁x₂ рассмотрим роазные варианты подстановки констант, в этом случае коньюнкция будет иметь вид:

k=x₁x₂+ax₁+bx₂+g

На каждом наборе a, b, g посчитаем fi.

Поскольку каждая из fi является результатом подстановки констант в f, то получим конъюнкцию и дизъюнкцию.

 

Функциональная полнота. Первая теорема о функциональной полноте.

Теорема:

Для того, чтобы система ф-ций была функционально полной в слабом смысле необходимо и достаточно, стобы она содержала хотя бы одну немонотонную и хотя бы одну не линейную ф-ции.

Необходимость:

Классы монотонных и линейных функций замкнуты и содержат константы 0 и 1, поэтому если система функций содержаит немонотонную и нелинейную ф-ции, то их нельзя получить с помощью суперпозиций ф-ций из F.

Достаточность:

Пусть система содержит нелинейную и немонотонную функции, тогда по лемме 1 из немонотонной функции можно получить отрицание, а по лемме 2 из нелинейной ф-ции можно получить дизъюнкции, конъюнкцию с использованием отрицания.

Пусть задана система функций F={×,Å}. Система ф-ций является полной в слабом смысле, так как конъюнкция является не линейной, а Å - немонотонной.

Является функция полной в слабом смысле так как она реализует константу 0, а константу 1 невозможно получить. Из того что конъюнкция – не лин. то по Лемме 2 можно получить дизъюнкцию и отрицание, т.к. сложение по модулю 2 – не монотонная то с его помощью можно получить отрицание.

 

Функциональная полнота. Теорема Поста.

Логические исчисления.

Особенностью человеческого мышления является способность к логическим рассуждениям, когда, имея некоторые предпосылки, истинность которых проверена на практике, мы получаем до утверждения, которые тоже истинны.

Опыт древних ученых был обобщен Аристотелем, который сформулировал конкретные виды рассуждений.

Аристотель рассмотрел 4 вида категорических рассуждения:

1. все А обладают свойством В.

2. некоторые А обладают свойством В.

3. все А не обладают свойством В.

4. некоторые А не обладают свойством В.

Были зафиксированы все случаи, когда из посылок такого вида выводятся предпосылки одного из этих видов.

(Пример: 1)все люди смертны, 2) Сократ – человек. Вывод – Сократ смертен)

Утверждения получили названия силлогизмы Аристотеля.

Наиболее часто используемые логические исчисления – это исчисления высказываний,. исчисления предикатов.

Высказывания. Формулы.

Высказывания

Элементы логических рассуждений – это утверждения, которые либо истинны, либо ложны.

Такие утверждения называются высказываниями.

Высказывания называются простыми, если они касаются 1 объекта. Обычно они обозначаются пропозициональными переменными, которые могут быть либо истинными, либо ложными.

Если пропозициональные переменные соединены между собой логическими связями, то получаем сложные высказывания (составные).

Название	Обозначение
отрицание	, не
конъюнкция	точечка, и
дизъюнкция	Галочка вниз, или
имплекация	Стрілка вправо, если _, то _

Пример: если "холодно" и "идет дождь", то "одеться тепло" и "взять зонт".

Формула

Формула – это правильно построенное пропозициональное высказывание. Для исчисления высказываний справедлива след. таблица истинности.