Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 4
Текст из файла (страница 4)
Это утверждение зачастую принимает форму угрозы, но мы рассмотрим более позитивный пример. Предположим, отец говорит сыну; "Если в этом семестре ты сдашь все экзамены на «отлично», я куплю тебе машину". Заметьте, что высказывание имеет вид; если р, то у, где р — высказывание В этом семестре ты сдашь все экзамены на «отлично», а д — высказывание Я куплю тебе машину. Сложное высказывание мы обозначим символически через р — у.
Спрашивается, при каких условиях отец говорит правду? Предположим, высказывания р и д истинны. В этом случае счастливый студент получает отличные оценки по всем предметам, и приятно удивленный отец покупает ему машину. Естественно, ни у кого не вызывает сомнения тот факт, что высказывание отца было истинным. Однако существуют еще три других случая, которые необходимо рассмотреть. Допустим, студент действительно добился отличных результатов, а отец не купил ему машину.
Самое мягкое, что можно сказать об отце в таком случае, — это то, что он солгал. Следовательно, если р истинно, а д ложно, то р — д ложно. Допустим теперь, что студент не получил положительные оценки, но отец тем не менее купил ему машину. В этом случае отец предстает очень щедрым, но его никак нельзя назвать лжецом. Следовательно, если р ложно и д истинно, то высказывание если р, то у (т.е. р — у) истинно. Наконец, предположим, что студент не добился отличных результатов, и отец не купил ему машину. Поскольку студент не выполнил свою часть соглашения, отец тоже свободен от обязательств.
Таким образом, если р и д ложны, то р — у считается истинным. Итак, единственный случай, когда отец солгал, — это когда он дал обещание и не выполнил его. Таким образом, таблица истинности для высказывания р — д имеет вид 24 ГЛАВА 1. Таблицы истинности, логика, доказательства Еще одним примером, который подтверждает таблицу истинности для импликации, является высказывание Если целое число равно 3, то его квадрат равен 9. Конечно, желательно, чтобы это высказывание было истинным всегда. Пусть р— высказывание Целое число равно 3, а д — высказывание Квадрат целого числа равен 9.
Если р и д истинны, то целое число равно 3 и его квадрат равен 9. Это соответствует первой строке таблицы истинности. Если целое число равно — 3, то его квадрат по-прежнему равен 9. В этом случае р ложно и а истинно, что совпадает со случаем 3 и подтверждает правильность третьей строки таблицы.
Если целое число равно 4, то ложны и р, и д, что соответствует случаю 4. Этим подтверждается правильность четвертой строки таблицы. Заметим, что случай 2 здесь не имеет места, но во всех других случаях эта таблица истинности обеспечила нам желаемый результат. Может показаться, что р- д носит характер причинно-следственной связи, но это не является необходимым.
Чтобы увидеть отсутствие причины и следствия в импликации, вернемся к примеру, в котором р есть высказывание Джейн управляет автомобилем, а д — утверждение У Боба русые волосы. Тогда высказывание Если Джейн управляет автомобилем, то у Боба русые волосы запишется как если р, то а или как То, что Джейн управляет автомобилем, никак причинно не связано с тем, что Боб русоволосый. Однако нужно помнить, что истинность или ложность бинарного сложного высказывания зависит только от истинности составляющих его частей и не зависит от наличия или отсутствия между ними какой-либо связи. ПРИМЕР 1.2. Требуется найти таблицу истинности для выражения (р — ~ а) Л (д — ~ г) .
Используя таблицу истинности для —, приведенную выше, построим сначала таблицы истинности для (р — д) и (д — г), учитывая, что импликация ложна только в случае, когда Т вЂ” Г. Случай р 9 т. Т Т Т Т Т Е Т Е Т Т Г Е Е Т Т Е Т Г Г Е Т Г Е Е Т Т Т Т Е Г Е Е 1 Т Т Т Т Е Е Р Г Т Т Т Т Т Е Т Е 2 1 Т Т Т Т Г Е Г Т Т Г Т Г Т Т Т Т Г Г Е Т Т Г Т Е 1 2 1 РАЭДЕЛ 7.2. Условные высказывания 25 Теперь используем таблицу для л, чтобы получить для высказывания (р — ~ д) Л (д — ~ т) таблицу истинности Случай р у т (р — у) Л (у — т) Высказывание вида (р — у) Л (у — р) обозначается через р у.
Символ называется эквиваленцией. Очевидно, таблица истинности для (р — д) Л (д — р) определяет таблицу истинности для р д. Случай р ц (р — у) Л (у — р) р+ т Т Т 1 Т Т 2 Т с 3 с Т 4 т т Т Т Т т с Т Т с с Т Т Т Непосредственно из определения вытекает, что эквиваленцня истинна только в случае, когда р и а имеют одинаковые истинностные значения. Может возникнуть вопрос о том, как интерпретировать такие выражения, как р Ч у, р Л дЧ т, р Л д - т и р Л д д'~т, в которых отсутствуют скобки.
Во избежание неоднозначности лучше всегда использовать скобки. Однако здесь, как и в алгебре, имеется приоритет выполнения операций. Операции выполняются в следующей последовательности:, Л, ~/, — и . Поэтому указанные выражения можно интерпретировать как (-р)чу, (рлдн)ч т, (рлдн) — ~ т и (р лу) ~-~ (д'~т). ° УПРАЖНЕНИЯ 1. Пусть р, д и т обозначают следующие высказывания; р: Он купит компьютер. о: Он будет праздновать всю ночь. Он выиграет в лотерею. Запишите следующие высказывания в виде символических выражений: а) Если он выиграет в лотерею, он купит компьютер и будет праздновать всю ночь.
1 Т Т Т 2 Т Т т 3 Т т Т 4 Т т с 5 т Т Т 6 с Т с 7 т т Т 8 с т т Т Т Т Т Т Т Т Т Т Т Г Т с т Т т с Г т Т Т Т К К Г т Т т Р Т Т Т Т Т Т с Т Т Г Т т с с Т с Т с Т Т с Т т Т т Т с 1 2 1 * 1 2 1 26 ГПКВА 1. Таблицы истинности, логика, доказательства б) Если он не купит компьютер, то и праздновать всю ночь не будет. в) Если он выиграет в лотерею, то будет праздновать всю ночь и если он не выиграет в лотерею, то не купит компьютер.
г) Если он не выиграет в лотерею или не купио компьютер, то праздновать всю ночь не будет. Пусть р, д и т обозначают следующие высказывания; р; Он читает комиксы. д: Он любит научную фантастику. т: Он — ученый-информатик. Запишите следующие высказывания в виде символических выражений; а) Если он чил|ает комиксы и любит научную фантастику, то он— ученый-информатик. б) Если он не читает комиксы и не любит научную фантастику, то он не является ученым-информатиком.
в) Если он читает комиксы, то он любит научную фантастику и если он не читает комиксы, то он — ученый-информатик. г) Если он — ученьсй-информатик, то он читает комиксы или он не любит научную фантастику. 3. Пусть р, д и т обозначают следующие высказывания р: Ему нравятся фиолетовые галстуки. о: Он популярен. т: У него странные друзья. Запишите следующие символические выражения в виде высказываний: а) (рлдн) — т; б) ув) р- (д'ит); г) (р- о) Л(о- т).
4. Пусть р, о и т обозначают следующие высказывания р: Он удачлив. Он популярен. т: Он богат. Запишите следующие символические выражения как высказывания: а) -(р- д); б) (ры т) — ~ д; в) о (рЛт); г) (р- у)Л( т- ( рЧ д)). 5. Постройте таблицы истинности для следующих выражений: а) (р — д)— б)р- (д- т); в) о- (рЛт) ((д — ~р)Л(у-~т)); г) ((р - а) ~ т) — (-р ~ -и).
6. Постройте таблицы истинности для следующих выражений: а) (р- д)- (д- т); РАЗДЕЛ 1.3. Эквивалентные высказывания 27 б) (р- д) У (гЛд); в) (р У т) †« (р Л «1); г) ((р — в) л т.) — (р ы г); д) ((р — д) л-(гч р)) (-р н-о). 7. Постройте таблицы истинности для следующих выражений: а) (р — в) (-д — р); б) (р л -(в «« -г)) (р о); в) (р ы г) †« в; г) ((р — «1) Л (д — г)) — (г — р); д) (р л в ч т)) — ((р л д)ч'1(р л г)). 8.
Постройте таблицы истинности для следующих выражений: а) ( (рЛ г)Чд) — «(«1««г); б) ((р Л «1) Ы т) «-«(г — ««1); в) ( (р — в) — (в — т)); г) (р '««1) Л (р - г); д) ((р ь« г) — «1) — ((р — о) '4 (𠆫 т)). 9. Укажите, какие нз следующих высказываний являются истинными: а) Если 2з=4, то За=9; б) Если2з=5, то3з=9; в) Если 2з = 5, то Зз = 10; г) Если 2з = 4, то Зз = 10. 10. Таблица истинности простого высказывания содержит две строки. Высказывание, состоящее из двух компонент, имеет таблицу истинности из четырех строк; сложное высказывание, составленное из трех простых, имеет таблицу истинности из восьми строк.
Сколько строк содержит таблица истинности высказывания, состоящего из четырех компонент? А если высказывание состоит из п компонент? 1.3. ЭКВИВАЛЕНТНЫЕ ВЫСКАЗЫВАНИЯ Особый интерес представляют сложные высказывания, имеющие различное строение, но являющиеся истинными в одних и тех же случаях. Такие высказывания называются логически эквивалентными.
Эквивалентность двух высказываний легко установить посредством сравнения их таблиц истинности. Например, пусть р и о обозначают высказывания р: Сегодня шел дождь. 9; Сегодня шел снег. Рассмотрим сложные высказывания Неверно, что сегодня шел дождь или снег, 28 ГЛЯВЯ К Таблицы истинности, логика, доказательстве или символически -(р М о), Сегодня не шел дождь и сегодня не шел снег, или символически Построим таблицы истинности для обоих высказываний. Случай р ц (з я) Итак, во всех четырех строках истинностные значения для (р и д) (обозначенные *) и для р л-д (обозначенные Ф) совпадают.
Это означает, что два рассматриваемых высказывания логически эквивалентны, т.е, -(рчо) = -р Л-е. Эквивалентность — очень полезное свойство; используя его, можно строить отрицание высказываний с "или", осуществляя отрицание каждой из его частей и меняя "или" на "и". С условным высказыванием — импликацией р — д — связаны еще три типа высказываний: конверсия, инверсия и контрапозиция высказывания р — д. Они определяются следующим образом: р — д импликация д — р конверсия высказывания р — у р — д инверсия высказывания р — д д — -р контрапозиция высказывания р — д Пусть дано высказывание-импликация Если он играет в футбол, то он популярен.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
