Глава 5. Сложное высказывание
1»
|
Составляющие простые высказывания:
А — Вчера было пасмурно;
В — Сегодня ярко светит солнце.
Форма сложного высказывания: ,.,
Е = А&В. '•" '
Пример 4.
Е = И добродетель стать пороком может, когда ее неправильно приложат. (У. Шекспир.)
Составляющие простые высказывания: ,
А = Добродетель неправильно приложат; i'(f
В = Добродетель стать пороком может. f" ''
Форма сложного высказывания: - ,'/«•'
,,, Е = А=*В.
В примерах 5 и 6 необходимо по форме высказывания и выраженным на естественном языке составляющим его простым высказываниям получить фразу на естественном языке.
Пример 5.
(A&~B)=*(C&D) Составляющие простые высказывания:
> i А = Человек с детства давал нервам властвовать над собой; I
В = Человек в юности давал нервам властвовать над собой; -л\\*
С = Нервы привыкнут раздражаться; „
D = Нервы будут послушны.
Фраза на естественном языке:
Е = Если человек с детства и юности своей не давал нервам властвовать над собой, то они не привыкнут раздражаться и будут ему послушны. (К. Д. Ушинский.)
Пример 6.
£ = (#&С).=М .
Составляющие простые высказывания: ■.»■.< -
А = Некто является врачом;
В = Больной поговорил с врачом; ;
С = Больному стало легче.
Фраза на естественном языке:
Е = Если больному после разговора с врачом не становится легче, то это не врач. (В. М. Бехтерев.)
Приоритет логических операций "^
При вычислении значения логического выражения (формулы) ло
гические операции вычисляются в определенном порядке, согласно их
приоритету: ' ' ' '
1) инверсия;
2) конъюнкция;
3) дизъюнкция;
4) импликация и эквивалентность.
Операции одного приоритета выполняются слева направо. Для изме
нения порядка действий используются скобки. , чг.
Продемонстрируем, как это делается, на конкретных примерах.
Пример 1.
| =>С& D<=> A . — инверсия; — конъюнкция; — дизъюнкция; — импликация; — эквивалентность. |
Дана формула:
Aw В-Порядок вычисления:
2) С & D
3)AvB
4)AvB=$C&D
5) Лу5=>С&£><=>!
Пример 2.
Дана формула:
Av(B=$C)&D<&,A
 | |
 |
*i___________________ Часть 1. Эдементы^матемздгичес&ойглргвки
Порядок вычисления: \ v ;.,t о ■■, ■■■■ • w- i.n :
1) А ■ ■ —инверсия; '\п'
2) (В => С) ■» — импликация в скобках;
3) (В => С) & D — конъюнкция;
4) Л v (5 => Q & £> _ — дизъюнкция;
5) Av(B=>C)&D<=>A —эквивалентность. , ,
О№
Построение таблиц истинности
сложных высказываний »к: ar*j .->f
Значение сложного высказывания определяется по таблице истинности. Рассмотрим примеры определения значений сложных высказываний.
Пример 1.
В классе оказалось разбито стекло. Учитель объясняет директору: Это сделал Коля или Саша. Но Саша этого не делал, так как в это время сдавал мне зачет. Следовательно, это сделал Коля. Прав ли учитель?
Формализуем данное сложное высказывание. Для этого сначала выделим составляющие простые высказывания и определим их количество (и):
К = Это сделал Коля.
С = Это сделал Саша.
п = 2. ; t
VI
Определим форму высказывания:
E = (KvC)&C=^K. ' '
■ ч *'»в",, >•■ .Определим количество строк и столбцов в таблице истинности. Так как каждое из простых высказываний может принимать всего два значения (0 или 1), то количество разных комбинаций значений п высказываний — 2". Количество строк в таблице равно 2" плюс 2 строки на заголовок. Количество столбцов в таблице равно сумме количества простых высказываний (и) и количества разных логических операций, входящих в сложное высказывание.
В нашем примере:
• количество строк — 22 + 2 = 6;
• количество столбцов — 2 + 4 = ё.М \\ ''•
Глава 5. Сложное высказывание
Начертим таблицу и заполним ее в соответствии с определениями логических операций последовательно по столбцам. Сначала заполняем 1-й и 2-й столбцы, затем вычисляем значения 3-го столбца по значениям 2-го, потом значения 4-го — по значениям 1-го и 2-го и т. д.:
| к | С | с (2) | KvC (1) v (2) | (KvQ&C (4)&(3) | (KvC)& ~С=>К (5)=»(1) |
Вывод: мы получили в последнем столбце все единицы. Это означает, что значение сложного высказывания истинно при любых значениях простых высказываний К и С. Следовательно, учитель рассуждал логически
правильно.
,. - и., -. j
Пример 2. If
Построим таблицу истинности для высказывания... .. [~-~ —1
Алгоритм построениятаблицы истинности сложного высказы
вания(на примере п = 3): ;
1. Вычислить количество строк и столбцов таблицы истинности.
Пусть сложное высказывание состоит из п простых. Тогда количество строк в таблице истинности равно 2" плюс 2 строки заголовка. Количество столбцов в таблице равно сумме количества переменных (л) и количества разных логических операций, входящих в сложное высказывание.
В высказывание Е входят 3 переменные: А, В, С(п = 3) и 4 логические операции: инверсия В, инверсия С, дизъюнкция, импликация, ч шипу»:; Имеем 23 + 2 = 10 строк и 3 + 4 = 7 столбцов.
2. Начертить таблицу и заполнить заголовок.
В первой строке заголовка записываем номера столбцов, во второй — промежуточные формулы в соответствии с приоритетом логических операций и в скобках условные записи операций над значениями пар столбцов, содержащие номера этих столбцов.
Часть 1. Элементы матешюнчес&ойгяогики
Глава 5. Сложное высказывание
'"'[ 3. Заполнить первые 3 столбца. ' ' '" " '
Количество строк со значениями переменных равно 8. 8:2 = 4: в 1-м столбце чередуем 4 нуля и 4 единицы. 4:2 = 2: во 2-м столбце чередуем 2 нуля и 2 единицы. ' ' 2:2=1:вЗ-м столбце чередуем 1 ноль и 1 единицу. '•• Таким образом, все возможные комбинации значений переменных учтены и никакие две не совпадают. Фактически такое заполнение столбцов соответствует двоичной записи чисел от 0 до 7.
4.Заполнить остальные столбцы.
Столбцы с 4-го по 7-й заполняем в соответствии с таблицами истинности соответствующих логических операций, причем при заполнении каждого столбца операции выполняются над значениями одного или двух столбцов, расположенных левее заполняемого.
Действуя по этому алгоритму, получим для нашего высказывания следующую таблицу:
| А | В | с | (2) | С (3) | A v Ъ (l)v(4) | A v £=> С (6)=> (5) |
Если в формулу входят 4 переменные, то соответствующая ей таблица истинности будет состоять из 24 = 16 строк со значениями; при 5 переменных в таблице имеем 25 = 32 строки со значениями.
Для любого сложного высказывания можно построить таблицу ис
тинности. Это следует из того, что количество входящих в него перемен
ных конечно и каждая из них может принимать всего два значения. (Заме
тим, что, например, для всех натуральных чисел такую таблицу постро
ить нельзя.) {v
Тождественно истинные, тождественно ложные и эквивалентные высказывания
Если высказывание истинно при всех значениях входящих в него переменных, то такое высказывание называется тождественно истинным или тавтологией (обозначается константой 1).
Например, высказывание Демократ — это человек, исповедующий демократические убеждения всегда истинно, т. е. является тавтологией.
Прогноз погоды на завтра может быть, например, таким:
Дождь будет или дождя не будет.
Такое предсказание будет всегда истинным, хотя вряд ли кого устро
ит. Его математическая запись: ц>,-
А vlj! "Л'.:
Проверить, является ли сложное высказывание тождественно истинным, можно по таблице истинности.
Мы видим, что во многих случаях, когда трудно установить, верно ли мы рассуждаем, всегда ли будет истинно наше утверждение, удобно применять средства математической логики.
Если высказывание ложно при всех значениях входящих в него переменных, то такое высказывание называется тождественно ложным (обозначается константой 0).
Например, высказываниеСегодня среда, а это — второй день недели является тождественно ложным.
Тождественно ложным является и следующее высказывание:
Компьютер включен, и компьютер не включен (выключен). • '>'
Математическая запись его такова:
А&А. "' ^>П '•'' '« :;0.'tV: -*-i
Если значения сложных высказываний совпадают на всех возможных наборах значений входящих в них переменных, то такие высказывания называют равносильными, или тождественными, или эквивалентными.
Часть 1. Элементы математической логики
Глава 5. Сложное высказывание
Равносильность высказываний А и В записывается с помощью знака равенства (=):
А =В.
Высказывания А и В равносильны {А ~ В) тогда и только тогда, когда их эквивалентность А <=> В является тождественно истинным высказыванием.
В качестве примера рассмотрим два высказывания: i
' Х=Не может быть, что Матроскин выиграл приз и отказалсяcirri Него: i
X = А & В '• •'
Y= Или Матроскин не отказался от приза, или не выиграл его. , |
Чтобы доказать равносильность (эквивалентность) сложных выска-зыванийХи Y, достаточно построить их таблицы истинности. Объединим эти две таблицы в одну:
| А | В | ~А~ (1) | (2) | А &.В (1)&(2) | х= А&В (5) | (3) v (4) | Х<=> Y (6) <=> (7) |
Существуют два варианта рассуждений:
1. Так как значения сложных высказываний X (5-й столбец) и Y (6-й столбец) совпадают на всех возможных наборах значений входящих в них переменных, то по определению Xравносильно Y.
2. Так как 8-й столбец содержит одни единицы, то эквивалентность X и /тождественно истинна, значит, Хи /равносильны.
i
■ ■ 1
Ш ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ
Простым называется высказывание, которое не содержит в себе других высказываний.
Если несколько простых высказываний объединены в одно с помощью логических операций, то такое высказывание называется сложным.
Вычисление значений логических выражений выполняется в определенном порядке, согласно их приоритету.
1) инверсия; '" ■'" "' '~Л
2) конъюнкция;
3) дизъюнкция; ' ..-<..■
4) импликация и эквивалентность. ' " * "-.'-'. . . , «
Операции одного приоритета выполняются слевадаправо;Дл&Язме-нения порядка действий используются скобки. ч, , \ . .< < .- Уи1- -
Алгоритм построения таблицы истинности сложного высказывания(на примере п = 3, где п — количество составляющих простых высказываний):
1. Вычислить количество строк и столбцов таблицы истинности.
Пусть сложное высказывание состоит из п простых. Тогда количество строк в таблице истинности равно 2" плюс 2 строки заголовка. Количество столбцов в таблице равно сумме количества переменных и количества логических операций, входящих в высказывание.
Для п = 3 имеем: 23 + 2 = 10 строк и 3 + 4 = 7 столбцов. ?'>■
2. Начертить таблицу и заполнить заголовок.
Первая строка заголовка — номера столбцов.
Вторая строка заголовка — промежуточные формулы и соответствующие им условные записи операций над значениями пар столбцов, содержащие номера этих столбцов.
3. Заполнить первые п столбцов. -•'•'• '•
Для и = 3 количество строк со значениями переменных равно 8.
8:2 = 4: в 1-м столбце чередуем 4 нуля и 4 единицы.
4:2 = 2: во 2-м столбце чередуем 2 нуля и 2 единицы.
2:2 = 1: в 3-м столбце чередуем 1 ноль и 1 единицу.
Таким образом, все возможные варианты учтены и никакие два не совпадают. Фактически такое заполнение столбцов соответствует двоичной записи чисел от 0 до 7.
4. Заполнить остальные столбцы.
Столбцы с 4-го по 7-й заполняем в соответствии с таблицами истинности соответствующих логических операций, причем при заполнении каждого столбца операции выполняются над значениями одного или двух столбцов, расположенных левее заполняемого.
Л
Часть 1. Элементы математической логики
Глава 5. Сложное высказывание
| л) (Л=>5)=»(Л=*5=»Л)- , |
| 1п^,.____ /i'lv^i--'■»' |
Если высказывание истинно при всех значениях входящих в него переменных, то такое высказывание называется тождественно истинным или тавтологией.
Если высказывание ложно при всех значениях входящих в него переменных, то такое высказывание называется тождественно ложным.
Если значения сложных высказываний совпадают на всех возможных наборах значений входящих в них переменных, то такие высказывания называют равносильными, тождественными, эквивалентными.
^ ВОПРОСЫ И ЗАДАНИЯ
1. Определите формы следующих сложных высказываний, записав
их на языке алгебры логики: '
а) Чтобы погода была солнечной, достаточно, чтобы не было ни
ветра, ни дождя.
б) Если у меня будет свободное время и не будет дождя, то я не буду
писать сочинение, а пойду на дискотеку.
в) Лошадь погибает от одного грамма никотина, но я не лошадь,
следовательно, курить вредно.
г) Без Вас хочу сказать Вам много,
При Вас я слушат ь Вас хочу.
д) Люди получают высшее образование тогда, когда они заканчива
ют институт, университет или академию.
2. Постройте таблицы истинности следующих сложных высказываний и определите, являются ли эти высказывания тождественно истиными:
а) А =» (В => А);
| ' ' , .*' it.' < > 1*Ь. ' Л',","' .' |
| ■ О => (А => В & Q); |
б) (A=>(B=>Q)=> ((А => В) =* (А => О);
в)А&В=>А;
г)А&В=*В;
Я)(А=>В)=>((А
e)A=>{BvA);
ж) В =» (5 v А);
з) (А => Q => ((В => Q => {A v В => Q);
и) {{А -> В) л (В -» Q) -»(А -> Q;
| •ч#»-:, V.1> ъ- ■.•ч'^тгТ- |
3. Определите;, какие из следующих пар высказываний являются экБивалентными, а ккакие нет: a)AwB;Bw:A; 6)Aw(BvQ;; (AvB)vC; B)Av(B&Qr, (A v В) & (A v Q; , t)AvA&B; /A;
j\)A=$B; B=> A;
e) A=^B&A;; AwB;
ж)А&В; В8&А;
з)А&(В&С)-у, (А&В)&С;
| < "it |
и) A & (В v Q); (A & В) v (A & Q; - > '.
K)A&(AvB);r A;
n)A<^B; (A=>B)&(B=$ A);
m)A=$B; A w В. -■■" ■' ' "'' '
, " ,\i -1*'' - i / .
/ ■■' %, • >.'..-■. - ■• ..r.U4o •, -, v '
u i \b ' " «' i л '"Г" " ' j«.V Г.
• . .мъ>"">* .*•'•.♦" ч" *s tv*\W. , д-' ,\ht'' .яге. «iirtd
| .;<,<? ,. | *; 11 | ,i,l | ' ,',<,Г 't..'V | ' * | !•>.•> - i | ■1 ■•>. |
| 't ., .i | u:\:- | - | !' 1'* ' | *:,„н^'.' | ||
| '•^.'Л | i"-i,' , ! • | i ., .*\'.\ • | :■ | |||
| Wt)> , > | \ | . v | ' > -j.T it' ,• | - " | ||
| % ' >f | ) | 4 . it: | j J; т «J | * ' | i |
Глава 6. Законы логики
Глава 6. Законы логики < * 1 1 "
-ф- ОБЪЯСНЕНИЕ МАТЕРИАЛА Законы формальной логики
Наиболее простые и необходимые истинные связи между мыслями выражаются в основных законах формальной логики. Таковыми являются законы тождества, непротиворечия, исключенного третьего, достаточного основания.
Эти законы являются основными потому, что в логике они играют особо важную роль, являются наиболее общими. Они позволяют упрощать логические выражения и строить умозаключения и доказательства. Первые три из вышеперечисленных законов были выявлены и сформулированы Аристотелем, а закон достаточного основания — Г. Лейбницем.