Тема 4.2 Алгебра логики. Модуль Алгебра логики Тема 1 Логические формулы и таблицы истинности
 Скачать 108.5 Kb.
|
|
Модуль 4. Алгебра логики Тема 4.1 Логические формулы и таблицы истинности. Основные понятия:.логическая формула, логическая операция,тавтология. Условные обозначения:
С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой.
В качестве примера рассмотрим высказывание “если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог”. Это высказывание формализуется в виде (A v B) C; такая же формула соответствует высказыванию “если Игорь знает английский или японский язык, то он получит место переводчика”. Как показывает анализ формулы (A v B) C , при определённых сочетаниях значений переменных A, B и C она принимает значение “истина”, а при некоторых других сочетаниях — значение “ложь” (разберите самостоятельно эти случаи). Такие формулы называются выполнимыми. Некоторые формулы принимают значение “истина” при любых значениях истинности входящих в них переменных. Таковой будет, например, формула А v  , соответствующая высказыванию “Этот треугольник прямоугольный или косоугольный”. Эта формула истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный. Такие формулы называются тождественно истинными формулами или тавтологиями. Высказывания, которые формализуются тавтологиями, называются логически истинными высказываниями.В качестве другого примера рассмотрим формулу А • , которой соответствует, например, высказывание “Катя самая высокая девочка в классе, и в классе есть девочки выше Кати”. Очевидно, что эта формула ложна, так как либо А, либо обязательно ложно. Такие формулы называются тождественно ложными формулами или противоречиями. Высказывания, которые формализуются противоречиями, называются логически ложными высказываниями.Если две формулы А и В “одновременно”, то есть при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными. Равносильность двух формул алгебры логики обозначается символом “=” или символом “”. Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы. Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера, поскольку основной системой счисления в компьютере является двоичная, в которой используются цифры 1 и 0, а значений логических переменных тоже два: “1” и “0”. Из этого следует два вывода:
В алгебре логики выполняются следующие основные законы, позволяющие производить тождественные преобразования логических выражений: ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ
Таблицы истинностиСогласно определению, таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы. Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре: (0,0), (0,1), (1,0), (1,1). Если формула содержит три переменные, то возможных наборов значений переменных восемь: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1). Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д. Удобной формой записи при нахождении значений формулы является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул. Примеры. 1. Составим таблицу истинности для формулы  , которая содержит две переменные x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах — значения промежуточных формул и в последнем столбце — значение формулы. В результате получим таблицу:
Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 1, то есть является тождественно истинной.2. Таблица истинности для формулы  :
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
- 
- задания во время чтения
- задания после чтения
