Главная   Онлайн инструменты по математической логике   Мат. логика теория   Как считает компьютер?   Схемы для ЭВМ    

Задание булевых функций посредством элементарных

Определение булевой функции
Элементарные булевы функции
Задание булевых функций посредством элементарных
Существенные и несущественные переменные
Эквивалентные функции
Основные эквивалентности
Функциональная полнота
Нормальные формы
Совершенные нормальные формы
Минимизация ДНФ методом Квайна
Карты Карно
Полином Жегалкина
Высказывания
Предикаты
Кванторы
Определение формальной теории
Исчисление высказываний
Теорема о дедукции. Полнота ИВ
Автоматическое доказательство теорем
Метод резолюций в ИВ
Определение алгоритма
Машина Тьюринга
Рекурсивные функции
Алгоритмически неразрешимые задачи
Алгоритмы и их сложности




     Если в логическую функцию вместо переменных подставить некоторые булевые функции, то в результате получается новая булевая функция, которая называется суперпозицией подставляемых функций (сложная функция). С помощью суперпозиции можно получать более сложные функции, которые могут зависить от любого числа переменных. Запись булевых функций через элементарные булевые функции будем называть формулой реализующей данную функцию.
     Пример: Пусть задана элементарная булева функция xvy. Подставим вместо x функцию x1↓x2. Получаем функцию трех переменных (x1↓x2)vy. Если вместо переменной y подставить, например, x3⊕x4, то получаем новую функцию от четырех переменных: (x1↓x2)v(x3⊕x4). Очевидно, что таким образом мы будем получать булевы функции, которые будут выражаться через элементарные булевы функции.
     Забегая вперед, отметим, что любая булева функция может быть представлена как суперпозиция элементарных функций. Для более компактной записи сложных функций введем следующие соглашения:
     1) внешние скобки опускаются;
     2) сначала производятся операции в скобках;
     3) считается, что приоритет связок убывает в следующем порядке: ¬, &, v, →, ∼. Для равносильных связок и оставшихся связок {⊕,|,↓}, следует пока расставлять скобки.
     Примеры: В формуле x·yvz скобки расставляются следующим образом: ((x·y)vz), т.к. операция & сильнее операции v согласно нашему соглашению.
     1. В формуле xvy∼z→x скобки расставляются следующим образом: ((xvy)∼(z→x)).
     2. В формуле (x⊕y)∼z→xyv¬z скобки расставляются следующим образом: ((x⊕y)∼(z→((xy)v(¬z)))).
     3. Формула x→y→z, следуя нашему соглашению, записана не корректно, т.к. расстановка скобок приводит к двум разным функциям: ((x→y)→z) и (x→(y→z)).

@ 2010 - 2017 tablica-istinnosti.ru Рейтинг@Mail.ru