Математическая логика
Высказывания и операции над ними. Формулы
жүктеу/скачать 0.93 Mb.
|
| 1. Высказывания и операции над ними. Формулы
Высказыванием называется всякое утверждение, о котором можно вполне определенно и объективно сказать истинно оно или ложно. Например, утверждение "2 > 0" является высказыванием и оно истинно, а утверждение "2 < 0" - ложно, утверждение "x2 + y2 = z2" высказыванием не является, так как оно может быть, как истинным, так и ложным при различных значениях переменных x, y, z. Высказывание полностью определяется своим истинностным значением. Условимся, значение истинности высказывания обозначать 1, если высказывание истинно, и 0, если высказывание ложно, что в точности соответствует значениям переменных булевых функций. Различают высказывания простые и сложные, высказывание называется простым, если никакая его часть не является высказыванием. Простые высказывания будем обозначать начальными заглавными буквами латинского алфавита A, B, C или A1, A2, . . .. Сложные высказывания характеризуются тем, что образованы из нескольких простых высказываний с помощью логических операций, т.е. являются формулами алгебры высказываний. Напомним, что алгебраической структурой или алгеброй называется структура, образованная некоторым множеством вместе с введенными на нём операциями. Определим алгебру высказываний. Обозначим через B = {0, 1} – множество высказываний. Определим операции на множестве B. Отрицанием высказывания A называется высказывание, которое принимает значение истина, если A ложно, и наоборот. Отрицание обозначается (А) и является унарной операцией. Пусть А и В - некоторые элементарные высказывания, введем бинарные операции над ними. Конъюнкцией высказываний A и B называется высказывание, которое принимает значение истина тогда и только тогда, когда истинны оба высказывания A и B. Обозначается конъюнкция - A B (АВ). Дизъюнкцией высказываний A и B называется высказывание, которое принимает значение истина, если истинно хотя бы одно из высказываний A или B. Обозначается дизъюнкция - A B. Импликацией высказываний A и B называется высказывание, которое принимает значение ложь тогда и только тогда, когда A истинно, а B ложно. Обозначается АВ. Эквиваленцией высказываний A и B называется высказывание, которое принимает значение истина тогда и только тогда, когда высказывания A и B имеют одинаковые значения. Обозначение операции - АВ (АВ). Логические операции определяются, также, с помощью таблиц, называемых таблицами истинности. Приведем сводную таблицу истинности для всех введенных логических операций.
Пропозициональной (высказывательной) переменной называется переменная, значениями которой являются простые высказывания. Обозначим высказывательные переменные через X1, X2, . . . , Xn. Понятие формулы алгебры высказываний вводится по индукции. Формулами алгебры высказываний являются: 1) логические константы 0 и 1; 2) пропозициональные переменные; 3) если А и В – формулы, то каждое из выражений (А), (А) (В), (А) (В), (А) (В), (А) ~ (В) есть формула; 4) других формул, кроме построенных по пп. 1) - 3), нет. Обозначим через M – множество всех формул алгебры высказываний, M является замкнутым относительно логических операций. Для формулы построенной по п. 3 формулы A и B называются подформулами. Число скобок в формуле можно сократить, Порядок выполнения операций в формуле определяется их приоритетом. Список логических операций в порядке убывания приоритета: ~. Изменение порядка выполнения операций, как и в алгебраических операциях, производится с помощью круглых скобок. В соответствии с таблицами истинности операций можно построить таблицу истинности формулы. Для этого необходимо: 1. Пронумеровать простые высказывания в алфавитном порядке. 2. Для каждого элементарного высказывания рассмотреть все возможные наборы значений истинности. Всего возможно 2n комбинаций, где n - число элементарных высказываний. Это количество строк в таблице. 3. Пронумеровать сложные высказывания, содержащие одну логическую операцию, затем сложные высказывания, содержащие две логических операции, и т.д., увеличивая сложность высказываний в соответствии с порядком выполнения операций. 4. Вычислить значения истинности всех сложных высказываний. Столбец с последним номером будет содержать значение истинности для всей логической формулы. Задание. Построить таблицу истинности формулы (АВ) АС. Решение. 1. Пронумеруем простые высказывания в алфавитном порядке А-1, В-2, С-3. 2. Каждый набор значений истинности элементарных высказываний изобразится набором 111, 110, 101 и т. д. Для нашего примера число комбинаций равно 8-ми, то есть таблица истинности будет содержать 8 строк. 3. Пронумеруем сложные высказывания формулы: АВ - 4; ( - 5; - 6; С - 7; конечная операция - 8. 4. Вычислим последовательно значения истинности сложных высказываний.
Формула называется выполнимой, если существует такой набор значений переменных, при которых эта формула принимает значение 1. Формула называется опровержимой, если существует такой набор значений переменных, при которых эта формула принимает значение 0. Формула называется тождественно истинной (ТИ-формулой) или тавтологией, если эта формула принимает значение 1 при всех наборах значений переменных. Формула называется тождественно ложной (ТЛ-формулой) или противоречием, если эта формула принимает значение 0 при всех наборах значений переменных. Так как логические формулы используются в операторах языков программирования и языков баз данных, то актуальными являются задачи определения эквивалентности, выполнимости, опровержимости, тождественной истинности и ложности формул. Такие задачи могут решаться с помощью построения таблиц истинности, однако существуют менее громоздкие способы решения этих задач. жүктеу/скачать 0.93 Mb. Достарыңызбен бөлісу:
| |||||||||||||||||||||||||||||||||||||||||