Составление простых и составных высказываний



Тема программы: Формулы логики. Таблицы истинности.

Цели урока:

1) Обобщить теоретические знания по теме: «Формулы логики. Таблицы истинности».

2) Рассмотреть алгоритмы решений заданий теме «Формулы логики. Таблицы истинности» .

3) Формировать ответственность; самоконтроль, рассудительность.

Время выполнения: 2 часа.

Теоретические основы

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

Простым высказыванием называют повествовательное предложение, относительно которого имеет смысл говорить, истинно оно или ложно.

Считается, что каждое высказывание либо истинно, либо ложно и ни одно высказывание не может быть одновременно истинным и ложным.

Примеры высказываний:

1. Москва – столица России.

2. Число 27 является простым.

3. Волга впадает в Каспийское море.

Высказывания 1 и 3 являются истинными. Высказывание 2 – ложным , потому что число 27 составное 27=3*3*3.

Следующие предложения высказываниями не являются:

  • Давай пойдем гулять.
  • 2*x>8.
  • a*x2+b*x+c=0.
  • Который час?

Итак, отличительным признаком высказывания является свойство быть истинным или ложным, последние четыре предложения этим свойством не обладают.

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

Примеры высказываний:

1. Сегодня светит солнце.

2. Трава растет.

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

В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно. Поэтому высказывание можно представить некоторой переменной величиной, значением которой может быть только 0 или 1. Если высказывание истинно, то его значение равно 1, если ложно - 0.

Простые высказывания назвали логическими переменными, а сложные - логическими функциями. Значения логической функции также только 0 или 1. Для простоты записи высказывания обозначаются латинскими буквами А, В, С.

Однако определение истинности высказывания далеко не простой вопрос. Например, высказывание «Число 1 +22 = 4294 967297 — простое», принадлежащее Ферма (1601-1665), долгое время считалось истинным, пока в 1732 году Эйлер (1707-1783) не доказал, что оно ложно. В целом, обоснование истинности или ложности простых высказываний решается вне алгебры логики. Например, истинность или ложность высказывания «Сумма углов треугольника равна 180°» устанавливается геометрией, причем в геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского — ложным.

В булевой алгебре простым высказываниям ставятся в соответствие логические переменные, значение которых равно 1, если высказывание истинно, и 0, если высказывание ложно. Обозначаются логические переменные, большими буквами латинского алфавита.

Существуют разные варианты обозначения истинности и ложности логических переменных:

Истина И True T 1
Ложь Л False F 0

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

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

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

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

Введем перечисленные логические операции.

Конъюнкция - логическое умножение (от латинского conjunctio - союз, связь):

  • в естественном языке соответствует союзу «И»
  • в алгебре высказываний обозначение «&»
  • в языках программирования обозначение «And».

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

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

Таблица истинности Диаграмма Эйлера-Венна
A B А&В
1 1 1
1 0 0
0 1 0
0 0 0

Итак, если два высказывания соединены союзом "И", то полученное сложное высказывание истинно тогда и только тогда, когда истинны оба исходных высказывания.

Дизъюнкция - логическое сложение (от латинского disjunctio - разобщение, различие):

  • в естественном языке соответствует союзу «ИЛИ» в алгебре высказываний обозначение «V» или «+»в языках программирования обозначение «Or».

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

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

Таблица истинности Диаграмма Эйлера-Венна
A B A + B
1 1 1
1 0 1
0 1 1
0 0 0

Итак, если два высказывания соединены союзом "ИЛИ", то полученное сложное высказывание истинно когда истинно хотя бы одно из составляющих высказываний.

Рассмотренные выше операции были двуместными (бинарными), т.е. выполнялись над двумя операндами (высказываниями). В алгебре логики определена и широко используется и одноместная (унарная) операция отрицание.

Инверсия - отрицание (от латинского disjunctio - разобщение, различие):

  • в естественном языке соответствует словам «неверно, что...» и частице «не»
  • в алгебре высказываний обозначение «» или «-»в языках программирования обозначение «Not».

Отрицание - логическая операция, которая с помощью связки «не» каждому исходному высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается.

В алгебре множеств логическому отрицанию соответствует операция дополнения до универсального множества, т.е. множеству получившемуся в результате отрицания множества А соответствует множество, дополняющее его до универсального множества.

Таблица истинности Диаграмма Эйлера-Венна
A А
0 1
1 0

Итак, если исходное выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное выражение ложно, то результат отрицания будет истинным.

Логическое следование (импликация):

Высказывание, составленное из двух высказываний при помощи связки «если ..., то ...», называется логическим следованием, импликацией (импликация от латинского implico - тесно связываю).

A B A=>B
1 1 1
1 0 0
0 1 1
0 0 1

A => B

"Из А следует В"

Итак, новое высказывание, полученное с помощью импликации, является ложным тогда и только тогда, когда условие (посылка А) - истинно, а следствие (заключение В) - ложно и истинно во всех остальных случаях.

Пример. Дано сложное высказывание: «Если выглянет солнце, то станет тепло». Требуется записать его в виде логической формулы. Обозначим через А простое высказывание «выглянет солнце», а через В - «станет тепло». Тогда логической формулой этого сложного высказывания будет импликация: A -> B.

Эквивалентность (логическое тождество):

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

A B А<=>В
1 1 1
1 0 0
0 1 0
0 0 1

A <=> B

"А равносильно В"

Итак, новое высказывание, полученное с использованием эквивалентности, является истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно

В алгебре логики логические связки и соответствующие им логические операции имеют специальные названия и обозначаются следующим образом:

Логическая связка Название логической операции Обозначения
не Отрицание, инверсия  
и, а, но Конъюнкция, логическое умножение &, •
или Дизъюнкция, логическое сложение V, +
если ..., то Импликация, следование =>
тогда и только тогда, когда эквивалентность, эквиваленция, равнозначность <=>

Примеры записи сложных высказываний с помощью обозначения логических связок:

1. "Быть иль не быть - вот в чем вопрос." (В. Шекспир) А V A <=> В

2. "Если хочешь быть красивым, поступи в гусары." (К. Прутков) А => В

 

Практические задания

Вариант 1                                                     Вариант 2

 

1. Установите, какие из следующих предложений являются логическими высказываниями, а какие — нет (объясните почему):

· "Солнце есть спутник Земли";

· "2+3?4";

· "сегодня отличная погода";

· "в романе Л.Н. Толстого "Война и мир" 3 432 536 слов";

· "Санкт-Петербург расположен на Неве";

· "музыка Баха слишком сложна";

· "первая космическая скорость равна 7.8 км/сек";

· "железо — металл";

· "если один угол в треугольнике прямой, то треугольник будет тупоугольным";

"если сумма квадратов двух сторон треугольника равна квадрату третьей, то он прямоугольный".

2. Укажите, какие из высказываний предыдущего задания истинны, какие — ложны, а какие относятся к числу тех, истинность которых трудно или невозможно установить.

3. Составьте таблицы истинности логических выражений:

· А Ú (B  C) .

· (А Ú B)  (A  B) .

· (А Ú B) Ú (C  B) .

Контрольные вопросы

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

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

3. Алгоритм построения таблиц истинности;

Список литературы

1.Аляев Ю.А. Тюрин С.Ф. Дискретная математика и математическая логика. — М.: Финансы и статистика, 2006. — 368 с.
2.Варпаховский Ф.Л. Элементы теории алгоритмов. - М., Просвещение, 1970. - 25 с. (МГЗПИ)
3.Гуц А.К. Математическая лоrика и теория алrоритмов. - Омск: Издательство Наследие. Диалог-Сибирь, 2003. - 108 с.
4.Босс В. Лекции по математике. Т. 6: От Диофанта до Тьюринга. - М.: КомКнига, 2006. - 208 с.
5.Босс В. Лекции по математике. Т. 10: Перебор и эффективные алгоритмы: Учебное пособие. — М.: Издательство ЛКИ, 2008. - 216 с.

4.

Практическое занятие № 8

Формализация высказываний.

Тема программы: Формулы логики. Таблицы истинности.

Цели урока:

 1) Обобщить теоретические знания по теме: «логические функции Microsoft Excel».

2) Рассмотреть алгоритмы решений заданий теме «логические функции Microsoft Excel», решить задачи.

 3) Формировать умение ставить цели и реализовывать их.

Время выполнения: 2 часа.

Теоретические основы

Логическая функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль. Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a, b).

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

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

1. инверсия;

2. конъюнкция;

3. дизъюнкция;

4. импликация;

5. эквивалентность.

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

Алгоритм построения таблиц истинности для сложных выражений:

1. Определить количество строк:

количество строк = 2n + строка для заголовка,

n - количество простых высказываний.

2. Определить количество столбцов:

количество столбцов = количество переменных + количество логических операций;

1. определить количество переменных (простых выражений);

2.определить количество логических операций и последовательность их выполнения.

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

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

D = А & (B Ú C).

Решение:

1. Определить количество строк:

на входе три простых высказывания: А, В, С поэтому n=3 и количество строк = 23 +1 = 9.

2. Определить количество столбцов:

o простые выражения (переменные): А, В, С;

o промежуточные результаты (логические операции):
А - инверсия (обозначим через E);
B Ú C - операция дизъюнкции (обозначим через F);
а также искомое окончательное значение арифметического выражения:
D = А & (B Ú C). т.е. D = E & F - это операция конъюнкции.

3. Заполнить столбцы с учетом таблиц истинности логических операций.

A B C E F E & F
0 0 0 1 0 0
0 0 1 1 1 1
0 1 0 1 1 1
0 1 1 1 1 1
1 0 0 0 0 0
1 0 1 0 1 0
1 1 0 0 1 0
1 1 1 0 1 0

 

Построение логической функции по ее таблице истинности:

Попробуем решить обратную задачу. Пусть дана таблица истинности для некоторой логической функции
Z(X,Y):

X Y Z
0 0 1
0 1 0
1 0 1
1 1 0

Составить логическую функцию для заданной таблицы истинности.

Правила построения логической функции по ее таблице истинности:

1. Выделить в таблице истинности те строки, в которых значение функции равно 1.

2. Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.

3. Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.

4. Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент взять с отрицанием.

Решение.

1. В первой и третьей строках таблицы истинности значение функции равно 1.

2. Так как строки две, получаем дизъюнкцию двух элементов: ( ) V ( ).

3. Каждый логический элемент в этой дизъюнкции запишим в виде конъюнкции аргументов функции X и Y: (X & Y) V (X & Y).

4. Берем аргумент с отрицанием если его значение в соответствующей строке таблицы равно 0 и получаем искомую функцию:
Z (X, Y) =( X & Y) V (X & Y).

Табличные процессоры

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

· ввод данных, в том числе и из баз данных;

· обработка данных (проведение инженерных, финансовых, статистических расчетов, сортировки, автоматического формирования итогов, агрегирования данных и т.д.);

· вывод информации, в том числе, в виде диаграмм и графиков.

Microsoft Excel

Одной из наиболее распространенных версий табличных процессоров является программа Microsoft Excel, в которой для различных типов вычислений имеется большое число встроенных функций: математических, статистических, финансовых, текстовых, информационных и др. Все функции разделены на категории, каждая из которых включает в себя определенный набор функций.
В состав встроенных функций Excel входят и логические функции (рис. 1), что позволяет более широко использовать табличный процессор для решения логических задач.

 

Рис. 1.Логические функции.


Для работы со сложными формулами в Excel реализован Мастер функций, хотя формулу можно вводить и непосредственно с клавиатуры. При конструировании формулы с помощью Мастера функций в диалоговом окне отображается имя функции, все ее аргументы, описание функции и каждого аргумента, текущий результат функции и всей формулы.
Одной из наиболее интересных функций является функция "ЕСЛИ" (рис. 2), которая позволяет реализовать ветвящуюся алгоритмическую структуру.

 

Рис. 2.Аргументы логической функции "ЕСЛИ".


Функции и выражения могут быть вложены друг в друга, в частности, функция "ЕСЛИ" в качестве значений аргументов "Значение_если_истина" и "Значение_если_ложь" допускает вложенность до 7 уровней, что позволяет конструировать проверку достаточно сложных условий.


Дата добавления: 2018-02-28; просмотров: 5151; Мы поможем в написании вашей работы!

Поделиться с друзьями:






Мы поможем в написании ваших работ!