Изучение элементов математической логики в школе на уроках информатики

Изучение элементов математической логики в школе на уроках информатики

Элементы математической логики всё больше проникают в школьное образование: это и математика (логические истинности), и информатика (понятия и законы математической логики, умения строить таблицы истинности и логические схемы, умения строить и преобразовывать логические выражения). Элементы логики, стали “обязательным компонентом школьного образования, усиливающим его прикладное и практическое значение”.

Особое место занимает понятие логически истинного предложения (логическая истина), оно является центральным логическим понятием, представляя логику в рассуждениях и в рассуждениях и доказательствах. Изучение логических истин – основная задача логики, вернее одна из основных задач. Однако, критерий истинности в логике не такой, как в естественных науках.

В естественных науках важна не форма, а содержание. Подтверждение истинности в естественных науках требует проведение эксперимента, наблюдений. В логике критерий истинности во многом определяется синтаксической структурой (формой) предложения. При аксиоматическом построении математики (в частности геометрии) теорему мы рассматриваем как некое условное предложение, логическую истинность которого доказываем.

Словологикаозначает совокупность правил, которым подчиняется процесс мышления. Сам термин "логика" происходит от древнегреческого «logos», означающего "слово, мысль, понятие, рассуждение, закон". Формальная логика - наука о формах и законах мышления. Законы логики отражают в сознании человека свойства, связи и отношения объектов окружающего мира. Логика как наука позволяет строить формальные модели окружающего мира, отвлекаясь от содержательной стороны. Основными формами мышления являются понятия, суждения и умозаключения.
     Понятие - это форма мышления, которая выделяет существенные признаки предмета или класса предметов, отличающие его от других. Например, компьютер, человек, ученики.
     Суждения- это форма мышления, в которой утверждается или отрицается связь между предметом и его признаком, отношения между предметами или факт существования предмета и которая может быть либо истинной, либо ложной. Языковой формой выражения суждения является повествовательное предложение. Вопросительные и побудительные предложения суждениями не являются.
     Суждения рассматриваются не с точки зрения их смысла и содержания, а только с точки зрения их истинности или ложности. Истинным будет суждение, в котором связь понятий правильно отражает свойства и отношения реальных объектов. "Дважды два равно четырем" - истинное суждение, а вот "Процессор предназначен для печати" - ложное. Суждения могут быть простыми и сложными. "Весна наступила, и грачи прилетели" - сложное суждение, состоящее из двух простых. Простые суждения (высказывания) выражают связь двух понятий. Сложные   состоят из нескольких простых суждений.
     Умозаключение - прием мышления, позволяющий на основе одного или нескольких суждений-посылок получить новое суждение (знание или вывод).
     Примерами умозаключений являются доказательства теорем в геометрии. Посылками умозаключения по правилам формальной логики могут быть только истинные суждения. Тогда и умозаключение будет истинным. Иначе можно прийти к ложному умозаключению.
     Математическая логика изучает вопросы применения математических методов для решения логических задач и построения логических схем, которые лежат в основе работы любого компьютера. Суждения в математической логике называют высказываниями или логическими выражениями. Подобно тому, как для описания действий над переменными был разработан раздел математики алгебра, так и для обработки логических выражений в математической логике была создана алгебра высказываний  или алгебра логики.

Логическое выражение - это символическая запись, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками).
     В булевой алгебре простым высказываниям ставятся в соответствие логические переменные, значение которых равно 1, если высказывание истинно, и 0, если высказывание ложно. Обозначаются логические переменные буквами латинского алфавита.
     Существуют разные варианты обозначения истинности и ложности переменных:

Связки "НЕ", "И", "ИЛИ" заменяются логическими операциямиинверсия, конъюнкция,дизъюнкция, импликации, эквивалентности. Это основные логические операции, при помощи которых можно записать любое логическое выражение. Алгебра логики работает на множестве, состоящем из двух значений: «истина», «ложь», которые в последующем мы будем для удобства обозначать, как 1и0

Основные операции логики высказываний

Инверсия, отрицание. Логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное – истинным

Обозначение: неA , ¬A,

Конъюнкция (логическое умножение) – сложное логическое выражение, которое является истинным только в том случае, когда истинны оба входящих в него простых выражения. Конъюнкция двух высказываний истинна в единственном случае, когда оба высказывания истинны

Обозначение: A иB,A∧B,A&B,A•B,

Дизъюнкция (логическое сложение) – это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно, если оба простых логических выражения ложны. Дизъюнкция двух высказываний ложна в единственном случае, когда оба высказывания ложны

Обозначение: A илиB,A∨B,A+B,AIB,

Импликация (логическое следствие) – это сложное логическое выражение, которое является ложным тогда и только тогда, когда условие истинно, а следствие ложно. Импликация двух высказываний ложна в единственном случае, когда условие (первое высказывание в импликации) истинно, а заключение (второе высказывание в импликации) ложно.

Обозначение:A→B

Эквиваленция, логическое равенство (эквивалентность) – это сложное логическое высказывание, которое является истинным только при одинаковых значениях истинности простых выражений, входящих в него. Эквивалентность двух высказываний истинна в двух случаях, когда оба высказывания одновременно истинны или одновременно ложны.

Обозначение:A↔B

Таблицы истинности для основных двоичных логических функций

Инверсия Конъюнкция Дизъюнкция        Импликация        Эквиваленция

Таблица истинности - таблица, показывающая,  какие значения (ложь либо истина) принимает составное высказывание при  всех сочетаниях (наборах)  значений  логических переменных, входящих в его состав.

Логическое выражение- составные высказывания, записанные в виде формулы.

Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак «=».

Порядок выполнения логических операций

При построении таблицы истинности необходимо учитывать порядок выполнения логических операций:

Инверсия

Конъюнкция

Дизъюнкция

Импликация

Эквиваленция

Алгоритм построения таблиц  истинности для логических функций с числом логических переменных равным 3 и превышающих 3:

1.    Подсчитать количество переменных n в логическом выражении.

2.  Определить число строк в таблице по формуле m=2ⁿ, где n - количество переменных.

3.  Подсчитать количество логических операций в логической формуле – d.

4.  Установить последовательность выполнения логических операций с учетом скобок и приоритетов.

5.  Определить количество столбцов L: число переменных + число операций L=n+d.

6.  Выписать наборы входных переменных.

7.  Провести заполнение таблицы истинности по столбцам, выполняя логические операции в соответствии с установленной в пункте 4 последовательностью.

Заполнение таблицы:

1.      Разделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1».

2.      Разделить колонку  значений  второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0».

3.      Продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами «0» или «1» до тех пор, пока группы «0» и «1» не будут состоять из одного символа.

Пример 1. Для формулы A/\ (B \/ ¬B /\¬C) построить  таблицу истинности. Решить уравнение: A/\ (B \/ ¬B /\¬C) = 1

Решение

Количество логических переменных n=3, следовательно, количество строк – m=2³ = 8.

Количество логических операций в формуле d= 5, количество логических переменныхn=3, следовательно количество столбцов –L= 3 + 5 = 8.

 Ответ: (1, 0, 0); (1, 1, 0); (1, 1, 1)

Пример 2. Определить истинность  логической функцииF(А, В) = (А\/В)/\(¬А\/¬В).

Определить значения логических переменных,  при которых эта функция F(А, В) = (А\/В)/\(¬А\/¬В) истинна.

Решение

1. В выражении две переменные А и В (n=2).

2. m_строк=2ⁿ,m=2²=4 строки.

3. В формуле d=5 логических операций.

4. Расставляем порядок действий

1) А\/ В;   2) ¬А;   3) ¬В;   4) ¬А\/¬В;   5) (А\/ В)/\(¬А\/¬В).

5.L_{столбцов}=n+d=2+5=7 столбцов.

Вывод: логическое выражение принимает значение истина на парах логических переменных (A,В) численно равных (0,1); (1,0)

Ответ: (0, 1); (1, 0)

 Пример 3.Постройте таблицу истинности для логического выражения

F(A,B,C) = (A\/B) /\ ¬С

Определите при каких логических значениях переменныхА, В, С логическая функция F(A,B,C)истинна.

Решение

В данной функции n=3 -три логические переменные – А, В, С

Количество строк таблицы – m=2³=8

В формуле d=3 логические операции.

Расставляем порядок действий

1) А\/ В;  2) ¬С; 3) (AVB) /\ ¬С .

Количество столбцов таблицы L = 3 + 3 = 6 

Из таблицы следует:F(A,B,C)истинна при А=0, В=1, С=0; А=1, В=0, С=0 и А=1, В=1, С=0

Ответ: (0,1,0); (1.0,0); (1,1,0)

Пример 4.  Определите истинность формулы:

F(A,B,C) = ((С \/В)→ В) /\ (А /\ В) → В

Построим таблицу истинности для этой логической функции.

 О
твет:формула является тождественно истинной при всех значениях логических переменных А, В, С.

Пример 5. СимволомF обозначено одно из указанных ниже логических выражений от трех аргументов:X,Y,Z.

Дан фрагмент таблицы истинности выраженияF:

 Какое выражение соответствует F?

 1) ¬X/\¬Y/\Z                      2) ¬X\/¬Y\/Z                 3) X\/Y\/¬Z              4) X\/Y\/Z

Решение(через построение таблицы истинности):

Чтобы решить данную задачу можно построить часть таблицы истинности для каждой из четырех функций, заданных в ответе для заданных наборов входных переменных, и сравнить полученные таблицы с исходной:

 Очевидно, что значения заданной функции F совпадают со значениями выраженияX\/Y\/¬Z.Следовательно, правильный ответ – 3.

Ответ: 3

Основные законы логики и их использование для упрощения составных логических функций и высказываний.

Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определённому виду путем использования основных законов алгебры логики.

Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.

Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).

Основные законы логики

Используя свойства исключения констант таблицы основных законов алгебры логики, мы можем оценить ложность, либо истинность любой логической функции или выражения с явно заданными значениями логических переменных, например:

а) F = (0 \/ 1) /\ (¬0 \/ ¬1) = (0 \/ 1) /\ (1 \/ 0) =1 /\ 1=1 - истина
б) F = (¬0 /\ ¬1) \/ (¬1 \/ ¬1) = (1 /\ 0) \/ (0 \/ 0) = 0 \/ 0 = 0 – ложь

c) F=(True →A)\/ (False \/¬True) =False \/ (False \/ False) = False \/ False = =False

Покажем на примерах как можно упростить логические выражения:

(A/\B) \/ (A/\¬B)

¬ (X \/ Y) /\ (X /\ ¬Y)

¬ X /\ Y \/ ¬ (X \/ Y) \/ X

Решение

(A/\B) \/ (A/\¬B) = A /\ (B \/ B)= A /\ 1 = A

Ответ: A

Решение Законы алгебры логики применим в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами.

     ¬ (X \/ Y) /\ (X /\ ¬Y) = (¬ X /\ ¬Y) /\ (X /\ ¬Y) =( ¬ X /\ X)/\(¬Y /\¬Y)= 0 /\¬Y=0 

2.1. ¬ (X \/ Y) = (¬ X /\ ¬Y) применили закон де Моргана

2.2. (¬ X /\ ¬Y) /\ (X /\ ¬Y) = =( ¬ X /\ X)/\(¬Y /\¬Y) = 0 /\¬Y= 0

Ответ: 0

  3)     Решение

¬X /\ Y \/ ¬ (X \/ Y) \/ X = (¬ X /\ Y) \/ (¬ X /\ ¬Y) \/ X=¬X /\ (Y \/ ¬Y) \/ X =

=¬X \/ X= 1

3.1. ¬ (X \/ Y)= ¬ X /\ ¬Y - применили в 3.1. правило де Моргана

3.2. (¬ X /\ Y) \/ (¬ X /\ ¬Y) = ¬ X /\ (Y \/ ¬Y) = ¬ X /\ 1 = ¬ X применили правило де Моргана 3.1., вынесли за скобки общий множитель ¬X

3.3. ¬ X \/ X= 1 - применили закон исключенного третьего

Ответ: 1

Задачи по теме

Определить истинность составного высказывания:

(или ) и (или );

(и ) или (и );

(или ) или (и );

(и ) или (или );

(или ) или (или );

(и ) и (и ).

Упростить логическое выражение:

, , , , , ;

, , ,

, , .

Построить таблицы истинности для следующих логических функций:

; ; ; ; ;

Для каких слов истинно высказывание "Первая буква гласная ИЛИ вторая буква гласная И последняя буква гласная": мороз, вариант, арбитр, акация, каша, газон, осень

Запишите наибольшее натуральное число X, при котором ложно высказывание (7+ X + 5 > 60) > (X • X > 80)?

Таким образом, данная статья дает инструмент для определения ложности или истинности сложных логических выражений (формул), знакомит учеников с алгоритмом построения таблиц истинности для сложных высказываний.

В ходе изучения данного материла на уроках информатики ученики знакомятся с такими понятиями, как “формальная логика”, “алгебра логики”, усваивают законы математической логики, осваивают основные логические операции, запоминают таблицы истинности, получают навыки построения таблиц истинности для сложных логических выражений.

В.Ю. Лыскова, Е.А. Ракитина Логика в информатике. — М. “Информатика и образование”. 1999 г.

И.Г. Семакин, Т.Ю. Шеина, Л.В. Шестакова Информатика и ИКТ. Профильный уровень. Учебник для 10 класса. М. БИНОМ, ЛБЗ, 2010 г., с. 363

Е.В. Андреева, Л.Л. Босова, И.Н. Фалина. Математические основы информатики. Методическое пособие. М. БИНОМ, ЛБЗ, 2007 г., с. 312

Е.В. Андреева, Л.Л. Босова, И.Н. Фалина. Математические основы информатики. Учебное пособие. М. БИНОМ, ЛБЗ, 2007 г., с. 327

http://ru.solverbook.com/spravochnik/tablicy/tablicy-istinnosti/

http://kpolyakov.spb.ru/school/ppt.htm

Адрес публикации: https://www.prodlenka.org/metodicheskie-razrabotki/175992-izuchenie-jelementov-matematicheskoj-logiki-v