Глава 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 строки на заголо­вок. Количество столбцов в таблице равно сумме количества простых высказываний (и) и количества разных логических операций, входящих в сложное высказывание.

В нашем примере:

• количество строк — 2² + 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 логические операции: инверсия В, инверсия С, дизъюнкция, импликация, ч шипу»:; Имеем 2³ + 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 переменные, то соответствующая ей табли­ца истинности будет состоять из 2⁴ = 16 строк со значениями; при 5 пере­менных в таблице имеем 2⁵ = 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 имеем: 2³ + 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.U₄o •, -, 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 "

-ф- ОБЪЯСНЕНИЕ МАТЕРИАЛА Законы формальной логики

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

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