Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Разложение функций алгебры логики по к переменным.

Введём обозначение .

тогда и только тогда, если .

Это позволяет записать элементарные конъюнкции высказываний в виде (точнее , но знак конъюнкции обычно опускают), где в качестве значений берётся 0 если входит в конъюнкцию с отрицанием, и 1 если без отрицания. Так же, элементарные дизъюнкции могут быть записаны в виде .

1) тогда и только тогда, если

Элементарная конъюнкция даёт 1 только на наборе переменных, в котором переменные, входящие в неё с отрицанием имеют значение 0, а переменные без отрицания 1.

2) тогда и только тогда, если

Элементарная дизъюнкция даёт 0 только на наборе переменных, в котором переменные, входящие в неё с отрицанием имеют значение 1, а переменные без отрицания 0)

Теорема. Всякую логическую функцию f(x)=f( x₁,x₂,x₃,…,x_n ) можно представить в виде

(Знак конъюнкции со списком переменных под ним обозначает, что берётся конъюнкция выражения при всех возможных значениях указанных переменных)

где 1 ≤ k ≤ n. Такое представление называется разложением функции по переменным.

Доказательство теоремы основано на том, что выбрав произвольный двоичный набор и подставив его в левую и правую часть мы получим: слева будет f (), а справа

Следствия:

1) Разложение по k-й переменной:

2) Разложение по всем переменным:

Из последнего утверждения следует теорема о представлении любой функции алгебры логики в сигнатуре алгебры логики: всякая функция алгебры логики может быть представлена в виде формулы, содержащей только операции конъюнкции, дизъюнкции и отрицания.