Дискретная математика (1). Лекция Составные высказывания
![]()
|
Логическое следствиеОпределение. Формула B есть логическое следствие формул A1, A2, .., An, если формула B принимает истинное значение при тех же значениях, при которых истинна каждая из формул A1, A2, .., An. Запись (A1, A2, .., An)B означает, что B – логическое следствие формул A1, A2, .., An. Пример. (AB, A ![]() ![]() Докажем данное следствие.
Из определения следует, что противоречие логически влечет любую формулу, а тавтология логически следует из любой формулы логики. Определение. Формулы F и G называются равносильными, если они являются логическими следствиями друг друга. Обозначение: ![]() Проанализировав последнее определение, получаем, что формулы равносильны, если они на всех наборах значений переменных превращаются в одинаковые по истинностному значению высказывания. Следующие теоремы связывают логическое следствие и импликацию, равносильность и эквиваленцию. Теорема1. ![]() Теорема2. ![]() Лекция 4. Булевы функции. Переменная х, принимающая значения 0 или 1, называется булевой (или логической, двоичной). Функция F, зависящая от булевых переменных ![]() ![]() Булевы функции F от n переменных ![]() ![]() ![]() В качестве примера рассмотрим таблицу истинности некоторой булевой функции F, зависящей от переменных ![]() ![]() ![]()
Булева функция n переменных F однозначно определяется ![]() Рассматриваемая булева функция F принимает значения 0 на наборах 000, 001, 011 и 100, а значение 1 на наборах 010, 101, 110 и 111. Множество наборов, на которых функция F принимает значение 1, называется характеристическим и обозначается через NF. В настоящем примере имеет место NF = (010, 101, 110, 111). Общее число различных булевых функций F от n переменных равно ![]() ![]() ![]() Элементарные булевы функции. Равносильности Булевых (или логических) функций от одной переменной ![]()
Основные элементарные булевы функции от двух переменных приведены в следующей таблице:
Функция ![]() ![]() ![]() ![]() ![]() ![]() Функция ![]() ![]() ![]() ![]() Кроме таблицы истинности, булевы функции могут быть заданы аналитически с помощью формул. Например, ![]() Если формула a реализует булеву функцию F,которая тождественно равна единице, то она называется тождественно истинной. Если формула a реализует булеву функцию F, которая тождественно равна нулю, то она называется тождественно ложной. Если формулы a и b зависят от одних и тех же переменных и реализуют одну и ту же булеву функцию F,то формулы a и b называются равносильными. Основные равносильности Закон двойного отрицания ![]() Идемпотентность ![]() ![]() Коммутативность ![]() ![]() Ассоциативность ![]() ![]() Дистрибутивность ![]() ![]() Законы де Моргана ![]() ![]() Формулы с константами ![]() ![]() ![]() ![]() ![]() ![]() Дополнительные равносильности ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Переменная ![]() ![]() ![]() ![]() ![]() |