Решение логических задач табличным методом Автор: к.ф.-м. наук Жанабергенова Г.К.

Основные понятия Ло́гика (др.-греч. λογική «наука о правильном мышлении», «способность к рассуждению» от др.- греч. λόγος «рассуждение», «мысль», «разум») др.-греч.др.- греч.«рассуждение», «мысль», «разум» Высказывание - это повествовательное предложение, о котором можно сказать истинно оно или ложно.

Умозаключение - это форма мышления, с помощью которой из одного или нескольких суждений может быть получено новое суждение (знание или вывод). Логическая переменная - это простое высказывание, содержащее только одну мысль. Ее символическое обозначение - латинская буква (например, A,B,X,Y и т.д.). Значением логической переменной могут быть только константы ИСТИНА и ЛОЖЬ (1 и 0). Составное высказывание - логическая функция, которая содержит несколько простых мыслей, соединенных между собой с помощью логических операций. Ее символическое обозначение - F(A, B...)

Логические связки Логическая связка Название Обозна- чение Высказы- вание Математическая запись 1 и конъюнкция логическое умножение, *, And A и В A B, A B A * B, A And B 2 или дизъюнкция логическое сложение +, Or A или В A B A + B, A Or B 3 не инверсия, логическое отрицание ¬, Not не А¬А, Not A 4Если…то импликация, логическое следование, Если A, то ВA B 5 тогда и только тогда эквивалентность, равносильность, логическое тождество, А тогда и только тогда, когда В А В, А В

Таблицы истинности Таблица истинности таблица, определяющая значение высказывания при всех возможных значениях простых высказываний Конъюнкция ДизъюнкцияИнверсия ИмпликацияЭквивалентность АВА^ВАВAvBА¬ААВАВАВ Вывод: результат будет ис- тинным тогда и только тогда, когда оба исходных высказывания истинны Вывод: результат будет ложным тог- да и только тогда, когда оба исходных высказывания ложны, и истинным в остальных случаях Вывод: результат будет ложным, если исходное выражение истинно, и наоборот Вывод: результат будет ложным тог- да и только тогда, когда из истинного основания (А) следует ложное следствие (В) Вывод: результат будет истинным тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны

Если составное высказывание (логическую функцию) выразить в виде формулы, в которую войдут логические переменные и знаки логических операций, то получится логическое выражение, значение которого можно вычислить. Значением логического выражения могут быть только ЛОЖЬ или ИСТИНА. При составлении логического выражения необходимо учитывать порядок выполнения логических операций, а именно: 1) действия в скобках; 2) инверсия (¬), конъюнкция (^), дизъюнкция (v), импликация (), эквивалентность ().

Пример 1 Построим таблицу истинности для выражения F = (AvB)&(¬Av¬B). Количество строк = 2 2 (2 переменных) + 1(заголовки столбцов) = 5. Количество столбцов = 2 логические переменные (А, В) + 5 логических операций (v, &, ¬, v, ¬) = 7. Расставим порядок выполнения операций: (AvB)&(¬Av¬B) АВAvB¬А¬В¬Av¬B(AvB)&(¬Av¬B)

Задача «Вернувшись домой, Мегрэ позвонил на набережную Орфевр. - Говорит Мегрэ. Есть новости? - Да, шеф. Поступили сообщения от инспекторов. Торранс установил, что если Франсуа был пьян, то либо Этьен убийца, либо Франсуа лжет. Жуссье считает, что или Этьен убийца, или Франсуа не был пьян и убийство произошло после полуночи. Инспектор Люка просил передать Вам, что если убийство произошло после полуночи, то либо Этьен убийца, либо Франсуа лжет. Затем звонила … - Все. Спасибо. Этого достаточно. – Комиссар положил трубку. Он знал, что трезвый Франсуа никогда не лжет. Теперь он знал все.» Что знал Мегрэ?

Решение задачи Пусть P=« Франсуа был пьян» L=«Франсуа лжет» I=«Этьен убийца» U=«Убийство произошло после полуночи» Тогда получим высказывание Так как, то Этьен - убийца

«История с амфорой». Алеша, Боря и Гриша нашли в земле сосуд. Рассматри­вая удивительную находку, каждый высказал по два предположения. Алеша: «Это сосуд греческий и изготовлен в V веке». Боря: «Это сосуд финикийский и изготовлен в III веке». Гриша: «Это сосуд не греческий и изготовлен в IV веке». Учитель истории сказал ребятам, что каждый из них прав только в одном из двух предположений. Где и в каком веке изготовлен сосуд?

«Это сосуд греческий» G; «Это сосуд финикийский» F; «Сосуд изготовлен в III веке» V 3 «Сосуд изготовлен в IV веке» V 4 «Сосуд изготовлен в V веке» V 5 Формализуем задачу, записав в данных обозначениях условия задачи.

Со слов учителя следует, что Алеша прав только в чем-то одном: или G = 1, или V 5 = 1. Таким образом, тождественно истинным будет высказывание: G¬V 5 v¬GV 5.=1 Аналогично, из слов Бори и учителя следует: F¬V 3 v ¬FV 3 = 1, а из слов Гриши и учителя: ¬G¬V 4 v GV 4 = 1. Кроме того, ясно, что сосуд может быть изготовлен только в одном из веков и только в одной из стран. Эти условия можно записать так: V3¬V4¬V 5 ˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5 = 1, F¬G v ¬FG = 1. Итак, мы получили пять тождественно истинных высказываний. Их нужно логически перемножить. Резуль­тат должен быть также тождественно истинным высказыванием.

1= (G¬V 5 v ¬GV 5 ) & (F¬V 3 v ¬FV 3 ) & (¬G¬V 4 v GV 4 ) & (F¬G v ¬FG)& (V3¬V4¬V 5 ˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5) = (упростим: сначала перемножим первую и третью скобки и вторую и четвертую скобки) =(G¬V 5 ¬G¬V 4 ˅ ¬GV 5 ¬G¬V 4 ˅ G¬V 5 GV 4 ˅ ¬GV 5 GV 4 )&( F¬V 3 F¬G ˅ ¬FV 3 F¬G ˅ F ¬V 3 ¬FG ˅ ¬FV 3 ¬FG) & (V3¬V4¬V 5 ˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5) = учитывая, что, G¬G = 0, GG = G,¬ G¬G =¬ G, упростим выражения в первой и второй скобках: =(¬GV 5 ¬V 4 ˅ ¬V 5 GV 4 ) &( ¬FV 3 G ˅ ¬V 3 F¬G)& (V3¬V4¬V 5 ˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5) = (перемножим первую и вторую скобки и упростим полученное выражение) (¬GV 5 ¬V 4 ¬FV 3 G ˅ ¬V 5 GV 4 ¬FV 3 G ˅ ¬GV 5 ¬V 4 ¬V 3 F¬G ˅ ¬V 5 GV 4 ¬V 3 F¬G) & (V3¬V4¬V 5 ˅ ¬V3V4¬V5 ˅ (¬V3¬V4V5)=(¬V 5 V 4 ¬FV 3 G ˅ ¬GV 5 ¬V 4 ¬V 3 F) & (V3¬V4¬V 5 ˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5)= ¬GV 5 ¬V 4 ¬V 3 F ¬GV 5 ¬V 4 ¬V 3 F=1, если ¬G=1, V 5 =1, ¬V 4 =1, ¬V 3 =1, F=1 Итак, сосуд финикийский и изготовлен в V веке.

Поход в кино Андрей, Аня и Маша решили пойти в кино. Каждый из них высказал свои пожелания по поводу выбора фильма. Андрей сказал: «Я хочу посмотреть французский боевик». Маша сказала: «Я не хочу смотреть французскую комедию». Аня сказала: «Я хочу посмотреть американскую мелодраму». Каждый из них слукавил в одном из двух пожеланий. На какой фильм пошли ребята?

Выделим простые высказывания и запишем их через переменные: А «Французский фильм» В «Боевик» С «Комедия» 2. Запишем логические функции (сложные высказывания). Учтем условие о том, что каждый из ребят оказался прав в одном предположении: а) «Французский боевик» ¬A&B ˅ A&¬B б) «Американскую мелодраму» ¬¬A&¬B ˅ ¬ А &¬¬В в) «Нефранцузская комедия» ¬¬A&C ˅ ¬A&¬C 3. Запишем произведение : (¬A&B ˅ A&¬B) & (¬¬A&¬B ˅ ¬ А&¬¬В)&( ¬¬A&C ˅ ¬A&¬C)=1.

Выделим простые высказывания и запишем их через переменные: А «Французский фильм» В «Боевик» С «Комедия» 2. Запишем логические функции (сложные высказывания). Учтем условие о том, что каждый из ребят оказался прав в одном предположении: а) «Французский боевик» ¬A&B ˅ A&¬B б) «Американскую мелодраму» ¬¬A&¬B ˅ ¬ А &¬¬В в) «Нефранцузская комедия» ¬¬A&C ˅ ¬A&¬C 3. Запишем произведение : (¬A&B ˅ A&¬B) & (¬¬A&¬B ˅ ¬ А&¬¬В)&( ¬¬A&C ˅ ¬A&¬C)=1.

Упростим формулу: (¬A&B ˅ A&¬B) & (¬¬A&¬B ˅ ¬ А&¬¬В)&( ¬¬A&C ˅ ¬A&¬C)= (¬A&B ˅ A&¬B) & (A&¬B ˅ ¬ А&В)&( A&C ˅ ¬A&¬C)= =(¬A&B& A&¬B ˅ A&¬B& A&¬B ˅ ¬A&B &¬А&В ˅ A&¬B&¬A&B)&( A&C ˅ ¬A&¬C)= =(A&¬B ˅ ¬A&B)&( A&C ˅ ¬A&¬C)= A&¬B& A&C ˅ ¬A&B& A&C ˅ A&¬B&¬A&¬C ˅ ¬A&B&¬A&¬C= = ¬A&B&¬C ˅ A&¬B&C =1

АВС¬A&B&¬C˅A&¬B&C Составим таблицу истинности для выражения: ¬A&B&¬C˅ A&¬B&C:

Найдем по таблице значения переменных, для которых F= Результат первой строки не является решением, т.к. в ответе Маши оба утверждения оказываются неверными, что проти­воречит условию задачи. Результат второй строки полностью удовлетворяет усло­вию задачи и поэтому является верным решением. Ответ: ребята выбрали американский боевик.

Спасибо за внимание