Игошин Математическая логика и теория алгоритмов (1019110), страница 8
Текст из файла (страница 8)
Остальные два столбца (для логических значений 2.(Х-ь У) и Ц У вЂ” > Х)) носят вспомогательный, промежуточный характер. Пример 2.4. Составим таблицу истинности для формулы Р(Р, О, й) м (Р л Ц) — > (Р <-ь .К). Она содержит три пропозициональные переменные, для которых имеются точно восемь различных наборов значений истинности. Таблица истинности для рассматриваемой формулы вместе с промежуточными столбцами выглядит следующим образом: Таблицу истинности формулы можно составлять в сокращенном виде.
Пример 2.5. Составим, например, такую таблицу для формулы: (Х л У) с-> ( Х ~~ У) (внешние скобки у формулы, согласно договоренности, опущены). В первой строке таблицы выпишем данную формулу. Под переменными Хи Увыписываем всевозможные наборы их логических значений.
Далее столбец под первым знаком ~ заполним логическими значениями формулы- У, исходя из соответствующих значений переменной У а столбец под знаком л — логическими значениями формулы (Хл ~У), исходя из соответствующих логических значений формул Хи У. Затем заполняем столбец под вторым знаком ~ значениями формулы ~Х и столбец под знаком ~~ — значениями формулы ( Х~ У). Наконец заполняем столбец под знаком <-~ логическими значениями данной формулы. В итоге получаем (х г)с->( х у) 001 О 110 000 О 111 11! О 000 100 О 011 Выделенные жирным шрифтом табулированные значения представляют собой столбец логических значений данной формулы. Практика составления довольно большого числа таблиц истинности есть наилучший способ прочно запомнить определения логических связок (отрицания, конъюнкции, дизъюнкции, импликации, эквивалентности) и довести до автоматизма выдачу значений любой из этих операций.
Это знание необходимо для решения более содержательных задач алгебры высказываний. Классификация формул алгебры высказываний. Формулы алгебры высказываний подразделяются на следующие типы: выполнимые, тавтологии, опровержимые и тождественно ложные. 30 Формула алгебры высказываний Г(Хь Х„..., Х„) называется выполнимой, если некоторая ее конкретизация является истинным высказыванием, т.е. существуют такие конкретные высказывания Аь Аь ..., А„которые, будучи подставленными в эту формулу вместо переменных Хь Х,, ..., Х соответственно, превращают ее в истинное высказывание.
Таким образом, Г(Хь Х~, ..., Х) выполнима, если существуют такие конкретные высказывания Аь Ам ..., А„, что З.(Г(Аь А,, ..., А„)) = 1. Выполнимой формулой является, в частности, формула, рассмотренная в примере 2.4. Она превращается в истинное высказывание, если, например, вместо пропозициональных переменных Р, (г, Я подставить ложные высказывания.
Выполнима также формула (Хл У) — > У, конкретизация которой рассмотрена в начале 5 2 (см. с. 23). Формула Г(Хь Хм ..., Х„) называется тавтологией, или тождественно истинной, если она превращается в истинное высказывание при всякой подстановке вместо переменных конкретных высказываний Аь Ам ..., А„, т.е. если 2.(Г(Аь Аь ..., А„)) = 1 для любых высказываний А,, А,, ..., А„. Формула из примера 2.3 является тавтологией. Для обозначения тавтологии используется знак м, который ставится перед формулой, являющейся тавтологией. Таким образом, запись и Г(Хь Х,, ..., Х„) означает, что формула Г(Х„ Х,, ..., Х„) является тавтологией. В частности, для указанного примера можем записать и (Х вЂ” ~ 1') ы (У-+ Х). Формула Г(Хь Хь ..., Х,) называется опровержимой, если существуют такие конкретные высказывания Аь Аь ..., А„, которые превращают данную формулу в ложное высказывание Г(А„Ам ..., А„), т.е.
) (Г(Аь А,, ..., А„)) = О. Другими словами, опровержимые формулы — это формулы, не являющиеся тавтологиями. Опровержимой является формула, рассмотренная в примере 2.4. Она обращается в ложное высказывание лишь тогда, когда вместо всех переменных Р, Д, й подставлены истинные высказывания. Формула (Х л 1') -~ У также опровержима. Наконец, формула Г(Х„Хм ..., Х„) называется тождественно ложной, или противоречием, если ЦГ(Ан Ам ..., А„)) = О для любых конкретных высказываний Аь А,, ..., А„. Другими словами, тождественно ложные формулы — это такие формулы, которые не являются выполнимыми. Примеры формул различных типов приведены в Задачнике (см. )ча 1.26 — 1.28). При решении задач на классификацию формул полезно отказаться от механического составления таблиц истинности и научиться решать их методом анализа структуры формУлы и нахождения тех отдельных наборов значений переменных, в случае которых формула принимает определяющее значение.
Мышление и математическая логика. В заключение следует отметить, что мы приступили к фундаментальному процессу исследования математическими методами такой сферы, как область 31 человеческого мышления. Начало процессу математизации логики положено математизацией языка. Фактически построена своеобразная знаковая система (символический язык логики высказываний), с помощью которой можно попытаться отразить человеческую мысль и проследить оформление мыслительного процесса.
Этот язык основывается на алфавите, состоящем из следующих символов: 1) пропозициональных букв: Р, Д, й, ...; 2) символов логических операций:, л, ~, -+, ~-~; 3) технических знаков: (, ). Словами построенного языка являются формулы логики высказываний. Предложения обычного (русского) языка могут быть «переведены» на символический язык логики высказываний, где они представляются формулами логики высказываний (см. Задачник, )ч«1.13, 1.14, и, особенно, 5 3). Следует иметь в виду, что при таком переводе сохраняются логическое содержание, логическая структура предложения, но конечно же теряются его языковая красота и психологические оттенки. Формула представляет собой формальную последовательность знаков, составленную по строгим правилам, нарушение которых недопустимо.
Такой перевод высказывания естественного языка на символический язык называется его формализацией. В частности, перевод высказывания на символический язык логики высказываний есть его формализация в рамках символической логики высказываний. Получаемая формула показывает способ соединения простых высказываний в составное при помощи логических союзов.
Она представляет как бы в «чистом виде» логическую структуру составного высказывания. Формула логики высказываний сама по себе не имеет никакого содержания. В частности, она не является ни истинной, ни ложной. Она превращается в высказывание, истинное или ложное, при всякой подстановке вместо всех ее пропозициональных переменных любых конкретных высказываний. Такой процесс подстановки называется интернретациейданной формулы алгебры высказываний. Таким образом, имеются два взаимно-обратных процесса (две процедуры): формализация и интерпретация.
Если имеется формула Ги высказывание А есть результат ее интерпретации, то сама формула Г будет формализацией высказывания А. Обратно, если имеется высказывание А и формула Г есть его формализация, то высказывание А будет одной из интерпретаций формулы Р Итак, формализация — это переход от высказывания естественного языка к формуле логики высказываний, а интерпретация — переход от формулы логики высказываний к высказыванию естественного языка. Таблица истинности или таблица значений формулы логики высказываний — это таблица, которая указывает логическое значение формулы при любой ее интерпретации.
32 Осознание этих понятий исключительно важно на данном этапе, поскольку они являются ключевыми для изучения в дальнейшем более глубоких разделов математической логики. На данном этапе делается первый шаг на пути формализации — важнейшего метода математической логики. 9 3. Тавтологии алгебры высказываний О значении тавтологий. Тавтологии представляют собой схемы построения истинных высказываний, независимо от содержания и истинности составляющих высказываний. Так, если для установления того, истинны или нет высказывания «Саратов основан в 1590 году», «Солнце вращается вокруг Земли», необходимо обладать специальными знаниями или заглянуть в специальную литературу, то для выяснения значения истинности высказываний «Треугольник АВС прямоугольный, или треугольник АВС не прямоугольный», «Неверно, что информация о наследственных признаках хранится в генах, и эта информация в генах не хранится» уже не нужно обладать знаниями ни в математике, ни в генетике.
Вывод об истинности последних высказываний делаем, исходя не из их содержания, а из их формы, структуры. Структура первого из последних высказываний выражается формулой Х ~ Х а второго — формулой — (Х л — Х). Легко убедиться в том, что обе эти формулы суть тавтологии. Данные формулы дают две схемы построения всегда истинных высказываний. И такова каждая формула, являющаяся тавтологией.
Но главное значение тавтологий не в этом. Основное значение тавтологий состоит в том, что некоторые из них предоставляют правильные способы построения умозаключений, т.е. такие способы, которые от истинных посылок всегда приводят к истинным выводам. А ведь именно такие рассуждения углубляют наши знания и обогащают их истинными сведениями. В частности, любая тавтология алгебры высказываний вида Г-» 6 соответствует некоторой общей схеме логического умозаключения. Поясним сказанное на примере следующей тавтологии указанного вила (внешние скобки опущены): (( Х-+ У) л (- Х-+ — У)) » Х (Проверьте, действительно ли данная формула является тавтологией.) Попытаемся выяснить, какой схеме логического умозаключения она соответствует. Схема логического умозаключения, описываемая данной тавтологией, часто используется в математических доказательствах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
