Спирина, М.С. Дискретная математика

цифрами 1 и 0 их семантическая характеристика — соответственно «истина» или «ложь». Например, высказывание «Город X располо­ жен на берегу Волги» (/4) может быть истинным (при X = Самара А = 1) или ложным (при X = Омск А = 0). Основными операциями являются: отрицание (не), дизъюнкция (строгая (либо) и нестрогая (или)), конъюнкция (и), импликация (если... то), эквива/ 1 енция (тогда и только тогда). Естественно, они определяются на основе введенных ранее соответствующих буле­ вых функций с учетом чисто логической специфики. Введем определения логических операций. Отрицанием, или инверсией, высказывания А называется вы­ сказывание А, которое истинно, когда высказывание А ложно, и ложно, когда А истинно. Дизъюнкцией (нестрогой или соединительной) высказыва­ ний А и В называется высказывание A v В, которое истинно тогда и только тогда, когда истинно хотя бы одно из этих вы­ сказываний. Конъюнкцией высказываний А и В называется высказывание АВ, которое истинно тогда и только тогда, когда истинны оба высказывания. Строгой дизъюнкцией высказываний А и В называется высказы­ вание А с В, которое истинно тогда и только тогда, когда истин­ но только одно из этих высказываний. Импликацией высказываний А и В называется высказывание А -э В, которое ложно тогда и только тогда, когда из истины сле­ дует ложь. Эквиваленцией высказываний А и В называется высказывание А <-» В, которое истинно тогда и только тогда, когда либо истин­ ны, либо ложны одновременно оба высказывания. Например, для простых высказываний «Максимов — хороший программист» (А) и «Он побеждает на олимпиадах» (В) можно составить сложные высказывания. Конъюнкция АВ: «Максимов — хороший программист, и он побеждает на олимпиадах» или «Максимов — хороший програм­ мист, он побеждает на олимпиадах». Нестрогая дизъюнкция A v В: «Или Максимов хороший про­ граммист, или побеждает на олимпиадах». Строгая дизъюнкция А с В: «Либо Максимов хороший програм­ мист, либо побеждает на олимпиадах». Импликация А -> В: «Если Максимов хороший программист, то он побеждает на олимпиадах»; «Для того чтобы Максимов по­ беждал на олимпиадах, достаточно , чтобы он был хорошим про­ граммистом». Эквиваленция А <->В: «Максимов хороший программист тогда и только тогда, когда он побеждает на олимпиадах». «Максимов хо­ роший программист только когда он побеждает на олимпиадах». 142