« Где начало того конца, которым оканчивается начало » Авторы: Машков Никита Абросимова Анастасия

Логические функции Логическая функция это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1. Логический элемент это устройство, реализующее ту или иную логическую функцию. Y=f(X1,X2,X3,...,Xn) логическая функция, она может быть задана таблицей, которая называется таблицей истинности.

Функции одной переменной Х01аргумент F000константа 0 F101Х F210Не Х F311константа 1

Функции двух переменных Таблица истинности функции двух переменных Y=F(X1,Х2) содержит 4 строки, а число функций двух переменных равно 16. Рассмотрим все эти функции двух переменных.

X10011 аргумент X20101 аргумент F00000 Константа 0 F10001 Конъюнкция F20010 Запрет по Х1 F30011 Повторение X1 F40100 Запрет по Х2 F50101 Повторение X2 F60110 Сложение по модулю 2 Функции двух переменных

F70111 Дизъюнкция F81000 Стрелка Пирса F91001 Эквивалентность F Не Х2 F Импликация x2-> x1 F Не Х1 F Импликация x1-> x2 F Штрих Шеффера F Константа 1 Функции двух переменных

Таблица истинности любой функции имеет вид: Таблица истинности функции где Yi принимают значения 0 или 1 Каждый элемент конъюнкции это дизъюнкция переменных Xi, если Xi = 1 в соответствующей строке или их отрицание, если Xi = 0 в соответствующей строке. Очевидно, что данный элемент конъюнкции равен 1 только для этой строки и 0 для всех остальных.

ТЕОРЕМА 1 Доказательство Таблица истинности любой функции имеет вид: где Y0, Y1, Y2, Y3 принимают значения 0 или 1. Составим конъюнкцию (ИЛИ) из всех строк, где Yi равно 1. Каждый элемент конъюнкции это дизъюнкция (И) переменных, если Xi = 1 в соответствующей строке или их отрицание, если Xi = 0 в соответствующей строке. Очевидно, что данный элемент конъюнкции равен 1 только для этой строки и 0 для всех остальных. Тогда, конъюнкция будет равна 1 только для Yi = 1 и 0 во всех остальных случаях. То есть данная конъюнкция будет равна исходной функции. Таким образом, исходная функция представляется через И,ИЛИ,НЕ. Любая функция двух переменных может быть представлена в виде комбинации функций И, ИЛИ, НЕ.

Представление функций через И-ИЛИ-НЕ 1.Штрих Шеффера X1 V X2

Представление функций через И-ИЛИ-НЕ 2.Стрелка Пирса X1 X2

Представление функций через И-ИЛИ-НЕ 3.Эквивалентность X1 X2 V X1X2

Представление функций через И-ИЛИ-НЕ 4.Импликация X1 V X2

Карты Карно

Минимизация функций Склейку клеток карты Карно можно осуществлять по единицам Склеивать можно только прямоугольные области, содержащие только единицы С точки зрения минимальности число областей должно быть как можно меньше.

ТЕОРЕМА 2 Доказательство Любая функция представима через И, ИЛИ, НЕ. Заменим в этом представлении данные функции их эквивалентом через другой базовый набор. Тогда исходная функция представляется через данный базовый набор, что и требовалось доказать. Для того, чтобы набор функций был базовым, то есть представлял все другие функции, достаточно чтобы через этот набор можно было представить функции И, ИЛИ, НЕ.

ТЕОРЕМА 3 Доказательство Чтобы функция штрих Шеффера была базовой достаточно представить через неё функции И, ИЛИ, НЕ. Отрицание Х1 = (Х1 1) = Х1|1 Конъюнкция Х1 Х2 = ( (Х1 Х2)) = (X1|X2) = (X1|X2)|1 Дизъюнкция Х1 Х2 = ( Х1 Х2) = Х1| Х2 = (Х1|1)|(Х2|1) Теорема доказана. Через функцию штрих Шеффера Y = X1|X2 = (X1 X2) можно представить любую другую логическую функцию.

Другие базовые функции Представление логических функций через стрелку Пирса (Теорема 4) Через функцию стрелка Пирса Y = X1 X2 = (X1 X2) можно представить любую другую логическую функцию. Представление логических функций через импликацию(Теорема 5) Через функцию импликация Y = X1 X2 = X1 X2 можно представить любую другую логическую функцию.

Выводы Логические функции являются математической основой современных вычислительных устройств. Для реализации логических функций в вычислительных устройствах важно унифицировать и минимизировать их представление. Любая логическая функция может быть представлена как комбинация базовых логических функций И, ИЛИ, НЕ. Для минимизации представления произвольных логических функций двух переменных можно использовать карты Карно. Приведены минимальные представления всех логических функций двух переменных через базовые функции И, ИЛИ, НЕ.

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