Теорема Жегалкина

Каждая функция из может быть представлена в виде полинома Жегалкина единственным образом.

Здесь единственность понимается с точностью до порядка слагаемых в сумме и порядка сомножителей в конъюнкциях:

, s = 0, 1,..., n. Доказательство. Любая функция из Р ₂ может быть представлена формулой над { x ₁ & x ₂, x ₁Å x ₂, 0, 1}, а эта формула после раскрытия всех скобок и приведения подобных членов дает полином Жегалкина. Докажем единственность представления. Рассмотрим функции f (x ₁,..., x_n) от n переменных. Мы знаем, что всего таких функций, т.е. их таблиц истинности, 2 ⁿ. Подсчитаем число различных полиномов Жегалкина от n переменных, т.е. число вариаций вида:. Число наборов равно числу всех подмножеств множества { x ₁,..., x_n }, сюда входит и пустое множество (если s = 0). Число подмножеств множества из n элементов равно 2 ⁿ, а так как каждый набор входит с коэффициентом, принимающим два значения: 0 или 1, то число всевозможных полиномов будет. Так как каждому полиному соответствует единственная функция, число функций от n переменных равно числу полиномов, то каждой функции будет соответствовать единственный полином.

12 вопрос применение логики высказываний к анализу и синтезу контактно релейных схем

Применение алгебры высказываний к синтезу и анализу контактных
схем основано на возможности интерпретировать булеву алгебру в терминах электрических цепей.

В этой интерпретации роль высказываний играют контакты, каждый из которых может быть замкнут или разомкнут. Знамению «истина» соответствует символ 1 - контакт замкнут. Значению «ложь» соответствует символ 0 - контакт разомкнут.

Дизъюнкции AvB соответствует схема, составленная из двух параллельно-соединенных контактов А и В. Действительно, схема, состоящая из двух параллельно соединенных контактов, пропускает ток тогда и только тогда, когда замкнут хотя бы один из контактов.

Конъюнкции А&В соответствует схема, составленная из двух последовательно соединенных контакт А и В. Действительно, схема, состоящая из двух последовательно соединенных контактов, пропускает ток тогда и только тогда, когда замкнуты оба контакта.

Отрицанию высказывания А соответствует размыкающий контакт А, управляемый тем же устройством, что и контакт А.

Таким образом, всякой функции алгебры логики можно поставить в соответствии электрическую схему, составленную из замыкающих и размыкающих контактов, которые соединяются последовательно или параллельно. Такие схемы называют «П-схемами» или схемами класса «П».

14 вопрос формальная система…..

Форма́льная систе́ма (форма́льная тео́рия, аксиоматическая теория) — результат строгой формализации теории, предполагающей полную абстракцию от смысла слов используемого языка, причем все условия, регулирующие употребление этих слов в теории, явно высказаны посредством аксиом и правил, позволяющих вывести одну фразу из других^[1].

Формальная система — это совокупность абстрактных объектов, не связанных с внешним миром, в котором представлены правила оперирования множеством символов в строго синтаксической трактовке без учета смыслового содержания, то есть семантики. Строго описанные формальные системы появились после того, как была поставлена задача Гильберта. Первые ФС появились после выхода книг Рассела и Уайтхеда«Формальные системы». Этим ФС были предъявлены определенные требования.