Оглавление:
Главная страница djvu-student.narod.ru
Электрический привод
Математическая логика
Биология
Бжд
История
Психология
Литература
Экономика
Химия
Информатика
Юриспруденция
Высшая математика
Школьная математика
Сопротивление материалов
Теоретическая механика
Теоретические основы электротехники
Физика
Программы, бесплатный софт
Обратная связь
Наша кнопка


Скачать эту страницу
в формате PDF, 149 КБ

Математическая логика, учебник

Учебник, часть 2

2. БУЛЕВЫ ФУНКЦИИ

2.1. Функции и константы алгебры логики

Пусть – множество, состоящее из двух элементов: 0 (ложь) и 1 (истина). Функцией алгебры логики или булевой функцией называется произвольная функция от аргументов, принимающая значения в . Будем предполагать, что функции от переменных определены для всех натуральных чисел , причем функциями от 0 переменных являются константы 0 и 1.

2.2. Несущественные переменные и равенство функций

Для того чтобы производить операции над функциями, например, из функций , , получить функцию , удобно предполагать, что области определения функций и совпадают. С этой целью вводиться понятие несущественной переменной. В данном примере функция рассматривается как функция от и , для которой переменная – несущественная.

Определение. Функция зависит существенным образом от аргумента , если существуют такие значения аргументов , что . В противном случае переменная называется несущественной или фиктивной. Две булевы функции называются равными, если одна из другой получается введением или удалением несущественных переменных.

Несущественные переменные удаляются следующим образом:

Сначала строится таблица значений функции . Затем перебираются пары строк аргументов, на которых значения функции совпадают, и отмечается -й элемент строк вида

Если, в результате, все элементы некоторого столбца окажутся отмеченными, то xj будет несущественной переменной.

Пример

. Здесь обозначает остаток от деления на 2. Составим таблицу значений:


доступна в файле для скачивания

Строку 1 сравниваем со строками, в которых . Отмечаем элементы 2-го столбца строк 1 и 3. То же самое проделываем с остальными строками. Отмечаем элементы 2-го столбца строк 2 и 4, 5 и 7, 6 и 8. Поскольку все элементы столбца 2 отмечены, то – несущественная переменная. Вычеркивая второй столбец, получаем таблицу значений некоторой функции , равной :


доступна в файле для скачивания

Функция фиктивных переменных не имеет. В общем случае некоторые строки таблицы значений могут отличаться лишь одним элементом, а функция может не иметь фиктивных переменных. Например, функция имеет таблицу:


доступна в файле для скачивания

и не имеет фиктивных элементов.

2.3. Специальные булевы функции

Рассмотрим следующие специальные булевы функции, на основе которых могут быть построены другие:

0, 1 – константы, могут рассматриваться как булевы функции от любого числа

переменных ;

– тождественная функция (или проекция );

– отрицание, обозначается также ;

– конъюнкция;

– дизъюнкция;

– сложение по модулю 2;

– стрелка Пирса;

– эквивалентность;

– импликация;

– штрих Шеффера.

Эти функции можно определить с помощью таблиц истинности:


доступна в файле для скачивания

2.4. Реализация функций формулами

Пусть – множество булевых функций. Понятие формулы над F определяется индуктивно:

  1. Каждая переменная и каждая булева функция из F являются формулами над F.

  2. Если – формулы над F, то для каждой функции из F выражение вида являются формулой над F.

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

  1. Интерпретация формулы сопоставляет элементу элемент .

  2. Интерпретация формулы принимает значения , где функции дополняются, в случае необходимости, фиктивными переменными.

Пример

Пусть . Тогда , , и – формулы над F, ибо

Подставляя в формулы, получим значения интерпретаций этих формул.

Если интерпретацией формулы g является булева функция f, то формула g называется реализацией функции f. Две формулы называются равносильными, если их интерпретации равны.

Например, формулы и 1, над , равносильны, ибо функция принимает значения 1, для всех .

Множество классов равносильных формул составляют булеву алгебру относительно операций:



доступна в файле для скачивания

которая называется алгеброй Линденбаума – Тарского.

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

2.5. Совершенная дизъюнктивная нормальная форма

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

Доказательство. Функция 0 реализуема с помощью формулы: . В общем случае имеет место равенство: , где обозначает , а . Здесь обозначает логическую сумму всех значений функции . Это приводит к равенству, доказывающему теорему: .

Правая часть этого равенства называется совершенной дизъюнктивной нормальной формой (СДНФ).

Пример 1

Найдем СДНФ для функции . С этой целью составим таблицу истинности:


доступна в файле для скачивания

Поскольку лишь на элементе значение функции равно 1, то .

Конъюнктивная нормальная форма определяется как конъюнкция формул вида: . В силу равенств получаем соотношение:

.

Это представление функции f называется ее совершенной конъюнктивной нормальной формой (СКНФ).


Пример 2

Найдем СКНФ функции . Составим таблицу истинности:


доступна в файле для скачивания

Так как лишь в случае и , то СКНФ будет равна: . Заметим, что СКНФ формулы будет равна: . Система булевых функций F называется полной, если каждая булева функция реализуема с помощью формулы над F. Поскольку , то имеет место следствие.

Следствие. Системы функций являются полными.

2.6. Минимизация методом карт Карно

Карты Карно – это графическое изображение таблиц истинности.

Пусть задана функция . Подмножество элементов , в которых , называется носителем функции f и обозначается через supp(f). Конечные пересечения подмножеств множества вида: называются кубиками. Кубики будут равны: , для некоторых и , таких, что . Если кубики являются максимальными, содержащимися в носителе, и попарно не пересекаются, то формула

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


Возможно превращение кубиков в квадраты и отрезки после отождествления противоположных сторон карты Карно, например:


доступна в файле для скачивания


доступна в файле для скачивания

Логические произведения состоят из сомножителей, значения которых не изменяются внутри кубика. Если это значение равно 1, то для переменной берется сомножитель , а если это значение равно 0 – то сомножитель .

Пример

Для булевой функции:

найти дизъюнктивную нормальную форму с наименьшим числом логических слагаемых.

Решение. Составим карту Карно:


доступна в файле для скачивания

Получаем 2 кубика: и . Внутри первого кубика не изменяются переменные и , и равны 0. Значит, первое слагаемое равно: . Внутри второго кубика не изменяются и , откуда второе слагаемое равно: . Следовательно, искомая дизъюнктивная нормальная форма равна: .

 Вверх...
Заметки:
» Тепловое оборудование, выбор и расчёт мощности
» Электропривод с двигателем постоянного тока приводит в движение лебедку
» Электротехника, решение задач это просто

Обучение за рубежём:
» Учеба в Великобритании
» Образование в Германии
» Образование в США
» Обучение во Франции

На этом сайте размещены ссылки на найденные в интернете книги, учебную литературу, интересный софт. Мы никак не связаны с сайтами, которые хранят научные труды на своих серверах. Все права принадлежат их авторам. Если у Вас есть авторские права на файлы и Вы не желаете чтобы они были доступны для поиска у нас, напишите нам.

Hosted by uCoz