Понятие булевой функции, примеры: релейно-контактные схемы

Естественно было бы выбирать для каждой булевой функции самую простую или одну из самых простых реализующих ее релейно-контактных схем. Поэтому упрощение релейно-контактных схем называется задачей анализа таких схем и является второй важной задачей теории релейно-контактных схем. Две релейно-контактные схемы, составленные из одних и тех же реле, называются равносильными, если одна из них проводит ток тогда и только тогда, когда другая схема проводит ток. Другими словами, две схемы, составленные из одних и тех же реле, равносильны, если они обладают одинаковыми функциями проводимости, зависящими от одних и тех же переменных. Из двух равносильных схем более простой считается та, которая содержит меньшее число контактов. Задача упрощения релейно-контактной схемы состоит в нахождении более простой равносильной ей схемы. Обычно она решается следующим образом. Для данной релейно-контактной схемы записывается ее функция проводимости. Затем эта функция с помощью тождественных преобразований, использующих известные свойства булевых функций, упрощается, т.е. сводится к функции, имеющей меньшее число вхождений переменных, нежели исходная функция. Наконец строится релейно-контактная схема, отвечающая упрощенной булевой функции.


Практическая часть
Задание 1
Доказать, что делится на 11 при любом n.
Решение
Докажем по индукции.
База индукции:




Докажем, что при выражение делится на 11.

Докажем, что делится на 11 при любом k.
Докажем по индукции:
База индукции:




Докажем, что при выражение делится на 11.


В общем, делится на 11, тогда и делится на 11.
Задание 2
Известно, что из 100 студентов живописью увлекаются 28, спортом - 42, музыкой - 30, живописью и спортом - 10, живописью и музыкой - 8, спортом и музыкой - 5, живописью, спортом и музыкой - 3. Определить количество студентов, ничем не увлекающихся.
Решение
Пользуемся диаграммой Венна:

Всего увлекающихся = (28+42+30)-(10+8+5)+(3) = 80
Ничем не увлекающихся студентов = 100-80

Задание 3
Упростить формулу . Проверьте правильность преобразований с помощью таблицы истинности исходной и полученной формулы.
Решение

Построим таблицу истинности, пользуясь следующими условиями:



a b c 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0
Задание 4
Привести к ДНФ и КНФ формулу:

Решение
Построим таблицу истинности:
x y 1 1 1 1 0 0 0 1 0 0 0 0
Построим ДНФ - это то значение, при котором функция принимает 1:

Построим КНФ:










10