Логические функции и таблицы их истинности.

Логические основы ЭВМ

(2 часа)

Цель и содержание

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

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

Теоретическое обоснование

Основные понятия математической логики

Математическая логика (Алгебра логики, Булева алгебра)— это раздел математики, изучающий высказывания и рассуждения, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.

Логическое высказывание - это любое утверждение, относительно которого можно сказать истинно оно или ложно, т.е. соответствует оно действительности или нет.

Так, например, утверждение "7 — нечетное число" следует считать высказыванием, так как оно истинное. Утверждение "Рим — столица Франции" тоже высказывание, так как оно ложное.

Очень часто трудно установить истинность высказывания. Так, например, высказывание "площадь поверхности Индийского океана равна 75 млн. кв.км" в одной ситуации можно посчитать ложным, а в другой — истинным. Ложным — так как указанное значение неточное и вообще не является постоянным. Истинным — если рассматривать его как некоторое приближение, приемлемое на практике.

Употребляемые в обычной речи слова и словосочетания "не", "и", "или", "если..., то", "тогда и только тогда" и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.

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

Например, из элементарных высказываний "Петров – врач", "Петров – шахматист" при помощи связки "и" можно получить составное высказывание "Петров – врач и шахматист".

Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.

Чтобы обращаться к логическим высказываниям, им дают имена. Пусть через Аобозначено высказывание "Тимур поедет летом на море", а через В — высказывание "Тимур летом отправится в горы". Тогда составное высказывание "Тимур летом побывает и на море, и в горах" можно кратко записать как А и В. Где "и" — логическая связка, А, В — логические переменные.

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

Каждая логическая связка рассматривается как логическая операция над логическими высказываниями и имеет свое название и обозначение.

В основе работы современных ЭВМ лежат три основные логические операции НЕ, ИЛИ, И. Иногда эти операции называют "тремя китами машинной логики".

Операция НЕ,выражается словом "не", называется отрицанием и обозначается знаком иличертой над логической переменной.

Операция И,выражается связкой "и", называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается знаком & (может также обозначаться знаками или *).

Операция ИЛИ,выражается связкой "или", называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком V или +. Высказывание А V В ложно тогда и только тогда, когда оба высказывания А и В ложны.

Используя операцииНЕ и ИЛИможно получить операцию ЕСЛИ-ТО.

Которая выражается связками "если ..., то", "из ... следует", "... влечет ...", называется импликацией (лат. implico — тесно связаны) и обозначается знаком →. А→B= А V В

Используя операцииНЕ, ИЛИ, Иможно получить операцию РАВНОСИЛЬНО.Которая выражаемая связками "тогда и только тогда", "необходимо и достаточно", "... равносильно ...", называется эквиваленцией или двойной импликацией и обозначается знаком ↔ или знаком ~.Высказывание A↔B истинно тогда и только тогда, когда значения А и В совпадают. А↔В = =(А V В)& (B V A).

Приоритет логических операций по убыванию: операции в скобках, операция отрицания, операция конъюнкции, дизъюнкция, импликация и в последнюю очередь – эквивалентность.

Логические функции и таблицы их истинности.

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

Логической функцией являются:

– всякая логическая переменная и символы "истина"("1") и "ложь"("0");

– составные высказывания: А, А & В, А v В, А →B, А ↔В (в

случае если А и В являются логическими функциями).

Используя вышеописанные логические функции можно образовать более сложные функции.

Значения каждой логической функции описывается таблицей истинности.

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

Для N переменных существует 2N всевозможных наборов значений переменных.

Например функция, которая содержит две переменные, имеет четыре (22 = 4) набора значений переменных: (0, 0), (0, 1), (1, 0), (1, 1).

Если функция содержит три переменные, то возможных наборов значений переменных восемь (23 = 8): (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1),

(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Составим таблицу истинности основных логических функций двух переменных (таблица 5.1).

Таблица 5.1 – Таблица истинности элементарных логических функций

X Y ØX X & Y X V Y X ® Y X « Y

 

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

Пример 5.1 Составить таблицу истинности для функции, которая содержит две переменные x и y, x&y v (x v y) v x (таблица 21.2.2).

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

Из таблицы 5.2 видно, что при всех наборах значений переменных x и y, функция x&y v ( x v y ) v xпринимает значение 1.

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

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

Таблица 5.2 – Таблица истинности для функции x&y v (x v y) v x.

Переменные Промежуточные логические функции Результат
X y x x&y x v y ( x v y) (x v y)vx x&y v (x v y)v x

 

Функция, которая принимает для некоторых наборов значений переменных значение "истина", а для других – значение "ложь", называется выполнимой логической функцией.

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

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