Тема 7. Перевод и запись различных выражений с естественного языка на язык алгебры логики.
Тема 7. Перевод и запись различных выражений с естественного языка на язык алгебры логики.
Цели урока:
1) научить учащихся переводить и записывать различные выражения с естественного языка на язык алгебры логики;
2) развивать логическое мышление;
3)воспитывать интерес к предмету.
Ход урока.
I. Орг. момент.
II. Повторение.
Какие из приведенных ниже выражений являются формулами логики высказываний, а какие нет?
• А+=> В;
• (+ p + q);
• p=> q => r ;
• (q + p) => r.
1,2 не являются формулами логики высказываний.
III. Новая тема.
Аппарат алгебры логики можно с успехом использовать для решения содержательных задач с запутанными исходными данными. Однако, прежде чем воспользоваться аппаратом алгебры логики, необходимо научиться правильно переводить высказывания естественного языка на символический язык алгебры логики. Как уже отмечалось, различают два вида высказываний: простые и сложные. Сложное высказывание состоит из двух или больше простых высказываний, соединенных с помощью логических операций. Логическое значение сложного высказывания зависит от значений составляющих его простых высказываний.
Рассмотрим несколько примеров.
1. Переведите на язык алгебры логики следующее высказывание: «Я поеду в Москву, и если встречу там друзей, то мы интересно проведем время».
Ведем следующие простые высказывания:
М – «я поеду в Москву»;
В – «встречу там друзей»;
И – интересно проведем время».
Формула: М ∙ (В=> И).
2. Переведите на язык алгебры логики следующее высказывание: «Если я поеду в Москву и встречу там друзей, то мы интересно проведем время».
Формула: (М ∙ В) => И.
3. Переведите на язык алгебры логики следующее высказывание: «Неверно, что если дует ветер, то солнце светит только тогда, когда нет дождя».
Ведем следующие простые высказывания:
В – «дует ветер»;
Д – «идет дождь»;
С — «светит солнце».
Запишем исходное высказывание на языке алгебры логики:
¬(В=> (¬С=> Д ))
4. Переведите на язык алгебры логики следующее высказывание: «Если будет солнечная погода, то ребята пойдут в лес, а если будет пасмурная погода, то ребята пойдут в кино».
Ведем следующие простые высказывания:
С – «солнечная погода»;
Р – «ребята пойдут в лес»;
К – «ребята пойдут в кино».
Запишем исходное высказывание на языке алгебры логики:
( С=> Р ) ∙ (¬С=> К ).
5. Найдите отрицание следующего высказывания и сформулируйте его на естественном языке: «Если урок информатики будет интересным, то никто из школьников — Миша, Вика, Саша — не будет смотреть в окно».
Введем следующие простые высказывания:
У – «урок информатики будет интересным»;
М – «Миша будет смотреть в окно»;
В – «Вика будет смотреть в окно»;
С – «Саша будет смотреть в окно».
Тогда:
¬ (У => (¬М ∙ ¬В ∙ ¬С))= ¬(¬У + (¬М ∙ ¬В ∙ ¬С))= У ∙ ¬ (¬М ∙ ¬В ∙ ¬С) = У ∙ (М+В+С).
Урок информатики будет интересным, но по крайней мере один из школьников будет смотреть в окно.
IV. Д/задание.
6. Переведите на язык алгебры логики следующее высказывание: « Неверно, что если погода пасмурная, то дождь идет только тогда, когда нет ветра».
Источник
f (x,у) = x Ú у
Построим таблицу истинности для дизъюнкции. Изобразим прямоугольником множество всех значений. Первый круг будет содержать значения множества А, второй круг значения множества В. Множеством А или В будет объединение этих кругов (на рисунке закрашена серым цветом). Будем «бросать» точку в прямоугольник с множествами. Результаты попадания во множество А, В и А или В внесем в левую таблицу. В правой таблице заменим попадание во множество А на х, В на у, попадание во множество А или В на f , «нет» на 0, «да» на 1. Правая таблица и есть таблица истинности для дизъюнкции.
В ЭВМ операция дизъюнкции физически реализуется стандартным логическим элементом «или» — дизъюнктером.
3) Конъюнкция (логическое умножение).
Соответствующие выражения языка:
· Х несмотря на Y
· Х в то время, как Y
f (x,у) = x & у
Построим таблицу истинности для конъюнкции. Изобразим прямоугольником множество всех значений. Первый круг будет содержать значения множества А, второй круг значения множества В. Множеством А и В будет пересечение этих кругов (на рисунке закрашена темно-серым цветом). Будем «бросать» точку в прямоугольник с множествами. Результаты попадания в множество А, В и А и В внесем в левую таблицу. В правой таблице заменим попадание во множество А на х, В на у, попадание во множество А и В на f , «нет» на 0, «да» на 1. Правая таблица и есть таблица истинности для конъюнкции.
В ЭВМ операция конъюнкции физически реализуется стандартным логическим элементом «и» — конъюнктером.
Реализуя первые три операции, можем построить любое устройство компьютера. Прежде, чем изучать последние две операции рассмотрим тему:
4) Импликация (логическое следование).
Соответствующие выражения языка:
· Х имплицирует Y
· Х достаточно для Y
· Y необходимо для Х
· Y тогда, когда Х
f (x) = x ® у
Построим таблицу истинности, для импликации используя выражение – не может из «истины» следовать «ложь».
В следует из А
В ЭВМ нет логического элемента, который реализует операцию импликации. Для реализации данной операции строиться комбиноторно — логическая схема. На основании таблицы истинности составляется булева функция (СДНФ – совершенная дизъюнктивная нормальная форма ).
Выписываем те строчки, где имеются 1 на выходе. Для всех таких наборов переменных запишем конъюнкции, инвертируя те переменные, которым соответствуют 0. Объединим полученные конъюнкции знаком дизъюнкции.
Анализируя, видим, что схема сложна и возникает желание упростить ее. Упрощение двоичных функций называется минимизацией.
Будем упрощать аналитически, используя закон логического склеивания.
5) Эквивалентность (логическая равнозначность ).
Соответствующие выражения языка:
· Х эквивалентно Y
· Х необходимо и достаточно для Y
· Х тогда и только тогда, когда Y
· Х если и только Y
· Х такое же, как и Y
f (x) = x
Построим таблицу истинности, подставляя в значения эквивалентности «Да», если А и В принимают одинаковые значения и «Нет» в случае различных А и В.
А эквивалентно В
В ЭВМ нет логического элемента, который реализует операцию эквивалентности. Для реализации данной операции строиться комбинаторно — логическая схема. На основании таблицы истинности составляется булева функция (СДНФ – совершенная дизъюнктивная нормальная форма ).
Выписываем те строчки, где имеются 1 на выходе. Для всех таких наборов переменных запишем конъюнкции, инвертируя те переменные, которым соответствуют 0. Объединим полученные конъюнкции знаком дизъюнкции.
Минимизацию двоичной функции произведем на основании закона де Моргана.
6) Построение одноразрядного двоичного сумматора.
Минимизировать z не представляется возможным, для представления z используют совершенную конъюнктивную нормальную форму (СКНФ).
Для всех наборов переменных, для которых функция равна нулю, записать дизъюнкции, инвертируя те переменные, которым соответствуют единичные значения, затем соединить дизъюнкции знаком конъюнкции.
Для дальнейшего упрощения воспользуемся законом де Моргана:
Решение логических (содержательных) задач
Одним из разделов логики является алгебра высказываний.
Высказывание – это предложение, о котором однозначно можно сказать истинно оно или ложно. Бывают простые и сложные (составные).
Основная задача – на основании истинности или ложности простых высказываний определить истинность и ложность составных высказываний.
Пример 1: Я поеду в Москву и если встречу там друзей, то интересно проведем время.
Решение: М – я поеду в Москву
В – я встречу там друзей М × ( В ® И )
И – мы интересно проведем там время
Пример2: Если я поеду в Москву и встречу там друзей, то интересно проведем время.
Решение: М × В ® И
Пример 3: Не верно, что если дует ветер, то солнце светит только тогда, когда нет дождя.
Решение: В – дует ветер
Д – идет дождь 
С – светит солнце
Пример 4: Если будет солнечная погода, то ребята пойдут в лес, а (и ) если пасмурная , то — в кино.
П – солнечная погода 
Пример 5: Не верно, что если погода пасмурная, то дождь идет тогда и только тогда, когда нет ветра.
Решение: Д – идет дождь
П – пасмурная погода 
Решение логических задач
I способ – с помощью таблиц истинности
Пример 6: Компьютер вышел из строя (нет изображения на экране монитора), однако неизвестно какое устройство не работает (монитор, видеокарта или оперативная память). Можно предположить следующее:
1) если монитор исправен или видео карта несправна, то оперативная память неисправна;
2) если монитор исправен, то оперативная память исправна.
Исправен ли монитор?
1. рассмотрим простые высказывания:
М = Монитор неисправен
В = Видеокарта неисправна
О = Оперативная память неисправна
2. Запишем на языке алгебры логики наши предположения: 
3. Пусть F (М,В,О) = 
4. Решить данную задачу – значит :
— составить таблицу истинности
— указать, при каких значениях М полученное сложное высказывание истинно.
Необходимо проанализировать все строки таблицы истинности, где F =1.
5. Составим для данного высказывания таблицу истинности: (самостоятельно)
Анализ таблицы показывает, что сложное высказывание истинно во всех случаях, когда М – истинно, т.е. вероятнее всего неисправен именно монитор.
II способ – с помощью преобразования логических выражений
Пример 7: Виктор, Роман, Леонид и Сергей заняли на математической олимпиаде четыре первых места. Когда их спросили о распределении мест, они дали три таких ответа:
1) Сергей – первый или Роман – второй
2) Сергей – второй или Виктор – третий
3) Леонид – второй или Виктор – четвертый.
Известно, что в каждом ответе только одно утверждение истинно.
Как распределились места?
Рассмотрим простые высказывания
S 1 = Сергей занял первое место
R 2 = Роман занял второе место
S 2 = Сергей занял второе место
V3 = Виктор занял третье место
L2 = Леонид занял второе место
V4 = Виктор занял четвертое место
На языке алгебры логики ответы ребят можно записать следующим образом:
Конъюнкция истинных высказываний истинна. Следовательно, имеет место равенство:
Раскрыв скобки и упростив это равенство (выполнить самостоятельно), получим:
Другими словами, места на олимпиаде распределились так:
Сергей — 1 место; Леонид – 2 место; Виктор – 3 место; Роман – 4 место.
Источник
Перевод функций в язык формальной логики
Перевод с естественного языка на язык логики предикатов
Перевести на естественный язык. Все честные ученые уважают друг друга.
Выберите правильный перевод на язык логики предикатов
Универсум – множество животных. Предикаты: A(x)=истина тогда и только тогда, когда животное x –.
Роль формальной логики в повседневном общении
тогда добавлю еще одну загадку: ученые провели опыт: поставили на весы человека и под.
Решение
В п. 3 «не было ни ветра, ни дождя» означает (not Wind) and (not Rain), а не not (Wind and Rain), потому что последнее эквивалентно (not Wind) or (not Rain).
п. 4: «для A необходимо B» означает A -> B. «Для A достаточно B» означает B -> A. То же замечание для п. 8.
п. 11: «A, разве что B» означает (not B) -> A (т.е., «если B, то ничего утверждать нельзя, а в остальных случаях A»).
Я предлагаю вам дать подробные пояснения, что непонятно. Например, я не вижу сложности в том, чтобы записать п. 6 «Неверно, что если погода пасмурная, то дождь идет тогда и только тогда, когда нет ветра» как not (Cloudy -> (Rain not Windy)).
Единственная сложность — со словом «значит». Я не согласен с автором задач, который, видимо, считает, что «A, значит B» переводится как A -> B. Дело в том, что «A, значит B» означает, что формула B логически следует из формулы A, то есть формула A -> B — тавтология (общезначима, тождественно истинна). Когда мы записываем, например, «Если идет дождь, то пасмурно» как Rain -> Cloudy, то получаем формулу, которая может быть истинна или ложна при разных истинностных значениях переменных Rain и Cloudy. Если же мы говорим «Идет дождь, значит сейчас пасмурно», мы делам утверждение, что всякий раз, когда формула Rain истинна, формула Cloudy также истинна. Это эквивалентно утверждению, что формула Rain -> Cloudy истинна при всех значениях переменных Rain и Cloudy. Но тот факт, что формула — тавтология, является утверждением мета-языка (обычного русского языка, на котором мы рассуждаем о формулах). Для него нет аналога в объектном языке пропозициональных формул. В обычной логике нельзя записать формулу, которая говорит, что формула является тавтологией. (Может быть, это возможно в модальной логике.) Можете передать вашему преподавателю, что фразы со словом «значит» нехорошо использовать в задачах по переводу высказываний с русского языка на язык формул.
Замкнутые классы и полнота систем булевых функций. Минимизация функций алгебры логики
1. Проверить, полна ли система функций А. 2. По заданной д.н.ф. D с помощью метода Блейка.
Язык логики
Здравствуйте! Интересуют следующие вопросы: 1. Записать математическую теорему на языке логики.
Язык логики предикатов
Записать на языке логики предикатов высказывание : «Через три точки, не лежащие на одной прямой.
язык логики предикатов
Помогите записать следующие определения на языку логики предикатов а) монотонной.
Источник