Решение логических содержательных задач различными способами. - презентация

1 Решение логических содержательных задач различными способами

2 Логические содержательные задачи Алгебра логики находит широкое практическое применение при решении логических содержательных задач. Исходными данными в таких задачах являются высказывания. Эти высказывания и взаимосвязи между ними бывают так сложны, что разобраться в них можно применяя специальные методы и способы. Логических содержательные задач разнообразны. Способов их решения тоже немало. Но наибольшее распространение получили следующие три способа : 1.средствами алгебры логики ; 2.табличный ; 3.с помощью рассуждений. Каждый из этих способов обладает своими достоинствами и недостатками. Однако аппарат алгебры логики позволяет построить универсальный способ решения таких задач.

3 Решение логических задач средствами алгебры логики Обычно используется следующая схема решения: 1.Изучается условие задачи; 2.Вводятся обозначения для простых логических высказываний; 3.Составляется логическая формула, описывающая логические связи (операции) между всеми высказываниями из условия задачи; 4.Определяются значения истинности этой логической формулы. Для этого строиться таблица значений формулы или полученное выражение упрощается с помощью законов алгебры логики ; 5.Из полученных истинных значений формулы определяются значения введённых простых логических высказываний, на основании которых делались заключение о решении. Рассмотрим решение задачи «Разбитое окно»

4 Логическая задача 1 Три школьника, Юра, Сергей и Даниил были вызваны к директору по поводу разбитого окна в кабинете. На вопрос директора о том, кто это сделал, мальчики ответили : Юра : « Даниил не бил окно. Это сделал Сергей ». Сергей : « Нет, это Даниил разбил стекло футбольным мячом, а Юра не мог этого сделать ». Даниил : « Сергей не разбивал. А я решал домашнюю задачу по алгебре.» Стало известно, что один из ребят оба раза солгал, а двое в каждом из своих заявлений говорили правду. Кто разбил окно в классе ?

5 Решение задачи 1) Введем обозначения для простых высказываний : a - Юра разбил окно ; b - Сергей разбил окно ; c - Даниил разбил окно. 2) Высказывания мальчиков запишем в виде формул : x1 = c & b x2 = c & a x3 = b 3) Составим единое логическое выражение для всех требований задачи : ( один мальчик солгал оба раза, два других сказали правду.) Х = x1 & x2 & b + x1 & (c & a ) & x3 + ( c & b ) & x2 & x3 4) Для исследования данной формулы можно построить таблицу значений при всех комбинациях простых высказываний или упростить формулу, используя аппарат алгебры логики. Однако построение таблицы истинности можно автоматизировать, составив программу на языке QBasic.

6 Логические переменные и операции в QBasic Переменных логического типа в QBasic нет, поэтому программирование логических операций имеет свои особенности : 1. Результат логической операции записывается в 2- х байтах ; 2. « ЛОЖЬ » - соответствует десятичный нуль 0; 3. « ИСТИНА » - соответствует десятичное 1. Основные логические операции : « отрицание » a NOT a « конъюнкция » a & b a AND b « дизъюнкция » a + b a OR b « импликация » a b a IMP b

7 Программа на языке QBasic REM разбитое окно CLS FOR a = -1 TO 0 FOR b = -1 TO 0 FOR c = -1 TO 0 x1 = NOT c AND b x2 = c AND NOT a x3 = NOT b X = (x1 AND x2 AND b) OR (x1 AND NOT c AND a AND x3) OR (c AND NOT b AND x2 AND x3) IF X THEN PRINT "a="; a; " b="; b; " c="; c NEXT c NEXT b NEXT a END Выражение X = ИСТИНА, если a=0, b=0, c=-1 Ответ : Окно разбил Даниил.

8 Сравнение различных способов решения логических содержательных задач Как правило логическую задачу можно решить несколькими способами ( методами ). Чтобы выбрать наиболее эффективный для каждой конкретной задачи надо знать достоинства и недостатки каждого способа. Табличный способ нагляден, но используется только для определенного класса задач и требует умения сравнивать и сопоставлять. Метод рассуждений подходит для решения только простых логических задач.

9 Сравнение различных способов решения логических содержательных задач Алгебраический способ наиболее трудоемкий, т. к. необходимо выразить высказывания в виде логических формул, значения которых надо вычислить. Знание законов алгебры логики позволяют облегчить этот процесс, а если это не удается сделать, то строиться таблица истинности. По значениям из таблицы можно найти решение. Однако, если количество простых высказываний велико или условия логической задачи запутанные или даже противоречивые, то построение и анализ таблицы истинности также является трудоемкой задачей. В этом случае используется программный способ решения логических задач. Создается программа, с помощью которой перебираются все допустимые значения простых высказываний и вычисляются значения единого логического выражения. Те простые высказывания, при которых выражение будет истинным и будут решениями логической задачи.

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

11 Литература 1. Андреева Е. В., Босова Л. Л., Фалина И. Н. Математические основы информатики. Учебное пособие. - М.: БИНОМ, Лыскова В., Ракитина Е. Логика в информатике. - М.: БИНОМ, Шауцукова Л. З. Информатика : Учебное пособие для кл. – М. Просвещение, 2005