ЛАБОРАТОРНАЯ РАБОТА № 1
Логические высказывания и формулы
Цель работы: изучение принципов построения сложных логических высказываний и реализация вычисления значений истинности с использованием средств программирования
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
Высказыванием (суждением) называется предложение, смысл которого можно выразить значениями: истина или ложь. Сложным называют суждение, состоящее из нескольких простых, связанных логическими связками, выражаемыми словами «и», «или», «не», «если – то».
Рассмотрим основные элементы формального описания логики высказываний.
1) Элементарные высказывания представляются переменными логического типа, принимающими значения «истина» (T) или «ложь» (F), и обозначающимися отдельными символами (как правило, заглавными буквами латинского алфавита):
«А.С. Пушкин – первый космонавт»: А = F;
«Железо – металл»: В = T.
2) Над логическими переменными вводятся следующие операции:
Ø Ù Ú ® «
3) Интерпретацией логического высказывания называется присвоение значения T или F каждому логическому символу и всему высказыванию в целом.
4) Сложные высказывания строятся из элементарных высказываний, связанных между собой логическими операциями, приведенными в п.2.
5) Понятие формулы алгебры высказываний.
В сложное высказывание (ХÚY) ® Z высказывания, после чего вся формула будет превращаться в некоторое составное высказывание. Переменные, вместо которых можно подставлять высказывания, т.е. переменные, пробегающие множество высказываний, называют пропозициональными переменными, или высказывательными переменными, или переменными высказываниями. Будем обозначать пропозициональные переменные заглавными буквами латинского алфавита Р, Q, R, S, X, Y, Z и т.д.
Формулы алгебры высказываний обладает следующими определяющими свойствами:
1. Каждая отдельно взятая пропозициональная переменная есть
формула алгебры высказываний.
2. Если F и К — формулы алгебры высказываний, то выражения Ø F, Ø _, (FÙ _), (FÚ _), (F® _), (F«_) — также являются формулами алгебры высказываний.
3. Никаких других формул алгебры высказываний, кроме полученных согласно п. 1 и 2, нет.
Значения истинности сложных высказываний часто описываются таблицами истинности. Таблица истинности содержит все возможные варианты значения истинности для элементарных суждений, и задаёт значение истинности выражениям для каждой возможной интерпретации (т.е. перечисляет все варианты для всевозможных комбинаций значений логических переменных).
Приведем таблицу истинности высказываний, полученных из двух простых высказываний (A и B) применением логических связок, описанных в п.2.
| A | B | ØA | AÙB | AÚB | A®B | A«B |
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
Следует отметить условие истинности операций импликации и эквивалентности:
Импликация имеет значение F тогда, когда предпосылка (символ перед знаком импликации) есть T, и значение истинности следствия (символа после знака импликации) есть F; иначе выражение имеет значение T.
Эквивалентность имеет значение T тогда, когда оба выражения имеют одинаковое значение истинности для всех возможных интерпретаций; иначе выражение эквивалентности имеет F.
Для построения таблицы истинности сложного высказывания придерживаются следующей последовательности шагов:
·Выписываются все возможные комбинации значений простых высказываний, составляющих рассматриваемое высказывание.
·Строится столбец с отрицаниями простых высказываний (если они фигурируют в рассматриваемом сложном высказывании).
·Строится столбец со значениями истинности операций, приведенных в скобках.
·Строится столбец со значениями истинности внешних операций.
Пример 1.1: построить таблицу истинности высказывания (A®B) Ù (ØAÚB)
| A | B | ØA | A®B | ØAÚB | (A®B) Ù(ØAÚB) |
| T | T | F | T | T | T |
| T | F | F | F | F | F |
| F | T | T | T | T | T |
| F | F | T | T | T | T |
Также допустима запись сокращенной таблицы истинности. В данном случае соответствующее значение записывается ниже, под рассматриваемой операцией (снизу приводится порядок заполнения сокращенной таблицы истинности).
Пример 1.2: построить сокращенную таблицу истинности высказывания (A®B) «(ØAÚB)
| A | ® | B | « | ØA | Ú | B |
| T | T | T | T | F | T | T |
| T | F | F | T | F | F | F |
| F | T | T | T | T | T | T |
| F | T | F | T | T | T | F |
В данном примере высказывание принимает значение истинности равное T при любых значениях, образующих его простых высказываний. Такие высказывания называются тавтологиями.
ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
1. Получить вариант сложного логического высказывания
2. Произвести интерпретацию пропозиционных переменных (с использованием арифметических вычислений и операций сравнения) и получить логическую формулу, на основе табуляции переменных Х и У.
3. На основе значений, полученных в п.2, вычислить значение истинности сложного логического высказывания. Результаты вычислений свести в таблицу.
Пример 1.3:
Дано сложное высказывание: ((А→В) Λ С) V В
Пусть простое высказывание
А: «(Х+3)<13»;
В: «(У-10)=0»;
С: «(Х+У)=10»;
Параметры табуляции: Х=1(0,5)2,5; У=-1(1)2
Интерпретация:
| Х | У | А: (Х+3)<13 | В: (У-10)=-8 | С: (Х+У)=0 | А→В | С | (А→В) Λ С | В | ((А→В) Λ С) V В |
| -1 | T | F | T | F | F | F | T | T | |
| 1,5 | T | F | F | F | T | F | T | T | |
| T | F | F | F | T | F | T | T | ||
| 2,5 | T | T | F | T | T | T | F | T |
4. Разработать блок-схему алгоритма и написать программу на
языке (Паскаль)V(С++/C#)V(Python) в соответствии с заданным вариантом.
5. Ввести, отладить и откомпилировать программу. Проверить правильность ее работы.
ВАРИАНТЫЗАДАНИЙ
| Х | У | А | В | С | высказывание | |
| Х=-1(0,5)2 | У=1(1)7 | (Х+0,5)>=0 | (Y+2)<5 | (2*X+Y)>4 | ((А→В) V С) →В | |
| Х=1(1)7 | У=-1(0,5)2 | (Y+0,5)>=0 | (X+2)<5 | (2*X+Y)>4 | ((А→В) Λ С) V В | |
| Х=0(1,5)9 | У=-3(1)3 | (Х-3)>=4 | abs(Y)<=1 | (X+Y*Y)>7 | ((А→В) Λ С) V В | |
| Х=-3(1)3 | У=0(1,5)9 | abs(X)<=1 | (Y-3)>=4 | (X+Y*Y)>7 | ((А→В) «С) V В | |
| Х=-5(2)7 | У=1(0,25)2,5 | (X*X-3Y)>10 | abs(X)>1 | (-3*X+Y*Y)>0 | ((А→В) V С) «_ | |
| Х=1(0,25)2,5 | У=-5(2)7 | abs(Y)>1 | (Y*X-3Y)>10 | (X+Y*Y)>0 | ((АV В) Λ С) → В | |
| Х= 1(0,5)2,5 | У=-1(1)2 | abs(X)<=1 | (Y-3)>=4 | (X+Y*Y)>7 | ((А«_) Λ С) → В | |
| Х=-1(1)2 | У= 1(0,5)2,5 | (X*X-3Y)>10 | abs(X)>1 | (-3*X+Y*Y)>0 | ((А→В) «С) V В | |
| Х=-1(0,5)2 | У=1(1)7 | (Y+0,5)>=0 | (X+2)<5 | (2*X+Y)>4 | ((А«_) Λ С) V В | |
| Х=-3(1)3 | У=0(1,5)9 | (Х-3)>=4 | abs(Y)<=1 | (X+Y*Y)>7 | ((А→В) Λ С) «_ | |
| Х=-1(1)2 | У= 1(0,5)2,5 | (X*X-3Y)>10 | abs(X)>1 | (-3*X+Y*Y)>0 | ((А&В) «С) → В | |
| Х=-1(0,5)2 | У=1(1)7 | (Y+0,5)>=0 | (X+2)<5 | (2*X+Y)>4 | ((А«C) Λ С) VВ |
СОДЕРЖАНИЕ ОТЧЕТА
·Вариант задания.
·Таблица истинности заданного логического высказывания.
·Таблица интерпретации логической формулы.
·Блок-схема алгоритма программы.
·Листинг программы с комментариями.
·Результаты контрольных расчетов, выводы.
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Дайте определение понятию «логическое высказывание».
2. Какой семантический смысл имеет операция импликации?
3. Определите значение истинности высказывания «Если Саратов расположен на Неве, то слоны — насекомые».
4. Какой семантический смысл имеет операция эквивалентности?
5. Определите значение истинности высказывания «15 делится на 6 тогда и только тогда, когда 15 делится на 3».
6. Посчитайте количество простых высказываний в составе сложного высказывания:
·Если производная функции в точке равна нулю и вторая производная этой функции в той же точке отрицательна, то данная точка есть точка локального максимума функции;
·Если в треугольнике любая его медиана не является высотой и биссектрисой, то этот треугольник не равнобедренный и не равносторонний.
7. Опишите последовательность шагов построения таблицы истинности сложного высказывания.