Логика, созданная как наука Аристотелем (384-322 г. до н.э.), на протяжении столетий использовалась для развития многих областей знания, включая теологию, философию, математику.
Она - тот фундамент, на котором построено все здание математики. По сути, логика — это наука о рассуждениях, которая позволяет определить истинность или ложность того или иного математического утверждения, исходя из совокупности первичных предположений, называемых аксиомами. Логика применяется также в информатике для построения компьютерных программ и доказательства их корректности. Понятия, методы и средства логики лежат в основе современных информационных технологий. Одна из основных целей этой работы — изложить основы математической логики, показать, как она используется в информатике, и разработать методы анализа и доказательства математических утверждений.
Логические представления - описание исследуемой сис-темы, процесса, явления в виде совокупности сложных высказываний, составленных из простых (элементарных) высказываний и логических связок между ними. Логические представления и их составляющие характеризуются опре-деленными свойствами и набором допустимых преобразо-ваний над ними (операций, правил вывода и т.п.), реализую-щих разработанные в формальной (математической) логике правильные методы рассуждений — законы логики .
Понятие высказывания
Высказывание — это утверждение или повествовательное предложение, о котором можно сказать, что оно истинно или ложно. Иными словами, утверждение об истинности или ложности высказывания должно иметь смысл. Истинность или ложность, приписываемые некоторому утверждению, называются его значением истинности , или истинностным значением.
Например, высказывания Дважды два четыре и Город Челябинск находится в азиатской части России истинные, а высказывания Три больше пяти и Река Дон в настоящее время впадает в Каспийское море ложны, так как не соответствуют действительности. Истинные высказывания принято обозначать T (true ) или И (истина ), а ложные, соответственно, F (false ) или Л (ложь ). В информатике истинность принято обозначать 1 (двоичная единица), а ложность - 0 (двоичный ноль).
Вот примеры предложений, не являющихся высказываниями:
Кто вы? (вопрос),
Прочтите эту главу до следующего занятия (приказ или восклицание),
Это утверждение ложно (внутренне противоречивое утверждение),
Площадь отрезка меньше длины куба (нельзя сказать истинно это предложение или ложно, т.к. не имеет смысла).
Мы будем обозначать высказывания буквами латинского алфавита р , q , r , Например, р может обозначать утверждение Завтра будет дождь , а q — утверждение Квадрат целого числа есть число положительное .
Логические связки
В обыденной речи для образования сложного предложения из простых используются связки — особые части речи, соединяющие отдельные предложения. Наиболее часто употребляются связки и , или , не , если ... то , только если , и тогда и только тогда . В отличие от обыденной речи, в логике смысл таких связок должен быть определен однозначно. Истинность сложного высказывания однозначно определяется истинностью или ложностью составляющих его частей. Высказывание, не содержащее связок, называется простым . Высказывание, содержащее связки, называется сложным . Логические связки также называют логическими операциями над высказываниями.
Пусть р и q обозначают высказывания
р: Джейн водит автомобиль,
q: У Боба русые волосы.
Сложное высказывание
Джейн водит автомобиль и у Боба русые волосы состоит из двух частей, объединенных связкой и . Это высказывание может быть символически записано в виде
где символ обозначает слово и на языке символических выражений. Выражение называется конъюнкцией высказываний р и q .
Встречаются также следующие варианты записи конъюнкции:
Точно так же высказывание
Джейн водит автомобиль или у Боба русые волосы.
символически выражается как
где обозначает слово или в переводе на символический язык. Выражение называется дизъюнкцией высказываний р и q .
Опровержение, или отрицание высказывания p обозначается через
Таким образом, если р есть высказывание Джейн водит автомобиль , то - это утверждение Джейн не водит автомобиль .
Если r есть высказывание Джо нравится информатика , то Джейн не водит автомобиль и у Боба русые волосы или Джо любит информатику символически запишется как
.
И наоборот, выражение
это символическая форма записи высказывания Джейн водит автомобиль, у Боба волосы не русые и Джо нравится информатика .
Рассмотрим выражение . Если некто говорит: "Джейн водит автомобиль и у Боба русые волосы" , то мы, естественно, представляем себе Джейн за рулем автомобиля и русоволосого Боба. В любой другой ситуации (например, если Боб не русоволос или Джейн не водит автомобиль) мы скажем, что говорящий не прав.
Возможны четыре случая, которые нам необходимо рассмотреть. Высказывание р может быть истинным (Т ) или ложным (F ) и независимо от того, какое истинностное значение принимает р , высказывание q может также быть истинным (Т ) или ложным (F ). Таблица истинности перечисляет все возможные комбинации истинности и ложности сложных высказываний.
Итак, конъюнкция истинна тогда и только тогда, когда истинны оба высказывания p и q , то есть в случае 1.
Точно так же рассмотрим высказывание Джейн водит автомобиль или у Боба русые волосы , которое символически выражается как . Если некто скажет: "Джейн водит автомобиль или у Боба русые волосы", то он будет не прав только тогда, когда Джейн не сможет управлять автомобилем, а Боб не будет русоволосым. Для того чтобы все высказывание было истинным, достаточно, чтобы одна из двух составляющих его компонент была истинной. Поэтому имеет таблицу истинности
Дизъюнкция ложна только в случае 4, когда оба р и q ложны.
Таблица истинности для отрицания имеет вид
Истинностное значение всегда противоположно истинностному значению р. В таблицах истинности отрицание всегда оценивается первым, если только за знаком отрицания не следует высказывание, заключенное в скобки. Поэтому интерпретируется как , так что отрицание применяется только к р . Если мы хотим отрицать все высказывание, то это записывается как .
Символы и называют бинарными связками, так как они связывают два высказывания. Символ ~ является унарной связкой, так как применяется только к одному высказыванию.
Еще одна бинарная связка - это исключающее или, которое обозначается через . Высказывание истинно, когда истинно p или q , но не оба одновременно. Эта связка имеет таблицу истинности
Используя слово или , мы можем иметь в виду исключающее или . Например, когда мы говорим, что р — либо истина, либо ложь, то, естественно, предполагаем, что это не выполняется одновременно. В логике исключающее или используется довольно редко, и в дальнейшем мы, как правило, будем обходиться без него.
Рассмотрим высказывание
,
где скобки использованы, чтобы показать, какие именно высказывания являются компонентами каждой связки.
Таблица истинности дает возможность однозначно указать те ситуации, когда высказывание является истинным; при этом мы должны быть уверены, что учтены все случаи. Поскольку сложное высказывание содержит три основных высказывания р
, q
и r
, то возможны восемь случаев
| Случай | p | q | r | |
||
| T | T | T | F | F | T | |
| T | T | F | F | F | T | |
| T | F | T | T | T | T | |
| T | F | F | T | F | T | |
| F | T | T | F | F | F | |
| F | T | F | F | F | F | |
| F | F | T | T | T | T | |
| F | F | F | T | F | F |
При нахождении значений истинности для столбца мы используем столбцы для и r , а также таблицу истинности для . Таблица истинности для показывает, что высказывание истинно лишь в том случае, когда истинны оба высказывания и r . Это имеет место лишь в случаях 3 и 7.
Заметим, что при определении значений истинности для столбца 
играет роль только истинность высказываний p
и . Таблица истинности для показывает, что единственный случай, когда высказывание, образованное с помощью связки или
, ложно, — это случай, когда ложны обе части этого высказывания. Такая ситуация имеет место только в случаях 5, 6 и 8.
Другой, эквивалентный способ построения таблицы истинности состоит в том, чтобы записывать истинностные значения выражения под связкой. Снова рассмотрим выражение. Сначала мы записываем истинностные значения под переменными р
, q
и r
. Единицы под столбцами истинностных значений указывают на то, что этим столбцам истинностные значения присваиваются в первую очередь. В общем случае число под столбцом будет показывать номер шага, на котором производятся вычисления соответствующих истинностных значений. Затем мы записываем под символом ~ истинностные значения высказывания . Далее записываем истинностные значения под символом . Наконец, записываем значения высказывания под символом .
| Случай | p | q | r | p | ((~ | q ) | r | ||
| T | T | T | T | T | F | T | F | T | |
| T | T | F | T | T | F | T | F | F | |
| T | F | T | T | T | T | F | T | T | |
| T | F | F | T | T | F | F | F | F | |
| F | T | T | F | F | F | T | F | T | |
| F | T | F | F | F | F | T | F | F | |
| F | F | T | F | T | T | F | T | T | |
| F | F | F | F | F | F | F | F | F | |
1.1.3. Условные высказывания
Допустим, некто утверждает, что если случится одно событие, то случится и другое. Предположим, отец говорит сыну: "Если в этом семестре ты сдашь все экзамены на «отлично», я куплю тебе машину ". Заметьте, что высказывание имеет вид: если р, то q , где р — высказывание В этом семестре ты сдашь все экзамены на «отлично» , а q — высказывание Я куплю тебе машину . Сложное высказывание мы обозначим символически через . Спрашивается, при каких условиях отец говорит правду? Предположим, высказывания р и q истинны. В этом случае счастливый студент получает отличные оценки по всем предметам, и приятно удивленный отец покупает ему машину. Естественно, ни у кого не вызывает сомнения тот факт, что высказывание отца было истинным. Однако существуют еще три других случая, которые необходимо рассмотреть. Допустим, студент действительно добился отличных результатов, а отец не купил ему машину.
Самое мягкое, что можно сказать об отце в таком случае, — это то, что он солгал. Следовательно, если р истинно, а q ложно, то ложно. Допустим теперь, что студент не получил положительные оценки, но отец тем не менее купил ему машину. В этом случае отец предстает очень щедрым, но его никак нельзя назвать лжецом. Следовательно, если р ложно и q истинно, то высказывание если р, то q (т.е. ) истинно. Наконец, предположим, что студент не добился отличных результатов, и отец не купил ему машину.
Поскольку студент не выполнил свою часть соглашения, отец тоже свободен от обязательств. Таким образом, если р и q ложны, то считается истинным. Итак, единственный случай, когда отец солгал, — это когда он дал обещание и не выполнил его.
Таким образом, таблица истинности для высказывания имеет вид
Символ называется импликацией , или условной связкой .
Может показаться, что носит характер причинно-следственной связи, но это не является необходимым. Чтобы увидеть отсутствие причины и следствия в импликации, вернемся к примеру, в котором р есть высказывание Джейн управляет автомобилем , а q — утверждение У Боба русые волосы . Тогда высказывание Если Джейн управляет автомобилем, то у Боба русые волосы запишется как
если p , то q или как .
То, что Джейн управляет автомобилем, никак причинно не связано с тем, что Боб русоволосый. Однако нужно помнить, что истинность или ложность бинарного сложного высказывания зависит только от истинности составляющих его частей и не зависит от наличия или отсутствия между ними какой-либо связи.
Рассмотрим следующий пример. Требуется найти таблицу истинности для выражения
.
Используя таблицу истинности для , приведенную выше, построим сначала таблицы истинности для и , учитывая, что импликация ложна только в случае, когда .
Теперь используем таблицу для , чтобы получить для высказывания
таблицу истинности
| Случай | p | q | r | (p | q ) | (q | r ) | |||
| T | T | T | T | T | T | T | T | T | T | |
| T | T | F | T | T | T | F | T | F | F | |
| T | F | T | T | F | F | F | F | T | T | |
| T | F | F | T | F | F | F | F | T | F | |
| F | T | T | F | T | T | T | T | T | T | |
| F | T | F | F | T | T | F | T | T | F | |
| F | F | T | F | T | F | T | F | F | T | |
| F | F | F | F | T | F | T | F | T | F | |
| * |
Высказывание вида обозначается через . Символ называется эквиваленцией . Эквиваленция также иногда обозначается как (не следует путать с унарной операцией отрицания).
Понятие «высказывание» первично. Под высказыванием в логике понимают повествовательное предложение, о котором можно говорить, что оно истинно или ложно. Любое высказывание либо истинно, либо ложно, и никакое высказывание не является одновременно истинным и ложным.
Примеры высказываний: есть четное число», «1 есть простое число». Истинностное значение первых двух высказываний - «истина», истинностное значение последних двух
Вопросительные и восклицательные предложения не являются высказываниями. Определения не являются высказываниями. Например, определение «целое число называется четным, если оно делится на 2» не является высказыванием. Однако повествовательное предложение «если целое число делится на 2, то оно четное» есть высказывание, и притом истинное. В логике высказываний отвлекаются от смыслового содержания высказывания, ограничиваясь рассмотрением его с той позиции, что оно либо истинно, либо ложно.
В дальнейшем будем понимать под значением высказывания его истинностное значение («истина» или «ложь»). Высказывания будем обозначать прописными латинскими буквами, а их значения, т. е. «истина» или «ложь» - соответственно буквами И и Л.
Логика высказываний изучает связи, которые полностью определяются тем, каким образом одни высказывания строятся из других, называемых элементарными. Элементарные высказывания при этом рассматриваются как целые, не разложимые на части, внутренняя структура которых нас не будет интересовать.
Логические операции над высказываниями.
Из элементарных высказываний с помощью логических операций можно получать новые, более сложные высказывания. Истинностное значение сложного высказывания зависит от истинностных значений высказываний, составляющих сложное высказывание. Эта зависимость устанавливается в данных ниже определениях и отражается в истинностных таблицах. В левых столбцах этих таблиц размещаются всевозможные распределения истинностных значений для высказываний, непосредственно составляющих рассматриваемое сложное высказывание. В правом столбце пишут истинностные значения сложного высказывания соответственно распределениям в каждой строке.
Пусть А и В - произвольные высказывания, относительно которых мы не предполагаем, что известны их истинностные значения. Отрицанием высказывания А называется новое высказывание, истинное тогда и только тогда, когда А ложно. Отрицание А обозначается через и читается «не A» или «неверно, что А». Операция отрицания полностью определяется истинностной таблицей
Пример. Высказывание «неверно, что 5 - четное число», имеющее значение И, есть отрицание ложного высказывания «5 - четное число».
С помощью операции конъюнкции из двух высказываний получается одно сложное высказывание, обозначаемое А Д В. По определению, высказывание А Д В истинно тогда и только тогда, когда оба высказывания истинны. Высказывания А и В называются соответственно первым и вторым членами конъюнкции А Д В. Запись «А Д В» читается как «Л и В». Истинностная таблица для конъюнкции имеет вид
Пример. Высказывание «7 - простое число и 6 - нечетное число» ложно, как конъюнкция двух высказываний, одно из которых ложно.
Дизъюнкцией двух высказываний А и В называется высказывание, обозначаемое , истинное в том и только в том случае, когда хотя бы одно из высказываний А и В истинно.
Соответственно этому высказывание А V В ложно в том и только том случае, когда и А и В оба ложны. Высказывания А и В называются соответственно первым и вторым членами дизъюнкции А V В. Читается запись А V В как «A или В». Союз «или» в данном случае носит неразделительный смысл, поскольку высказывание А V В истинно и при истинности обоих членов. Дизъюнкция имеет следующую истинностную таблицу:
Пример. Высказывание «3 Высказывание, обозначаемое , ложное в том и только в том случае, когда А истинно, а В ложно, называется импликацией с посылкой А и заключением В. Высказывание А-+ В читается как «если А, то 5», или «A влечет В», или «из A следует В». Истинностная таблица для импликации такова:
Отметим, что между посылкой и заключением могут отсутствовать причинно-следственные связи, но это не может повлиять на истинность или ложность импликации. Например, высказывание «если 5 - простое число, то биссектриса равностороннего треугольника является медианой» будет истинным, хотя в обычном понимании второе не следует из первого. Истинным также будет высказывание «если 2 + 2 = 5, то 6 + 3 = 9», поскольку истинно его заключение. При данном определении, если заключение истинно, импликация будет истинной независимо от истинностного значения посылки. В том случае, когда ложна посылка, импликация будет истинна независимо от истинностного значения заключения. Эти обстоятельства кратко формулируют так: «истина следует из чего угодно», «из ложного следует все, что угодно».
Среди суждений, устанавливающих различные отношения между математическими понятиями, выделяют высказывания и высказывательные формы.
Высказыванием называется предложение,
относительно которого
имеет смысл вопрос, истинно оно или ложно. .
Например, предложение «Число 6 четное» есть истинное высказывание, а предложение «2 + 4 = З 2 » -ложное высказывание.
В математике различают элементарное и составное
высказывание.
Предложение «Число 28 делится на 7» элементарное. Составными
высказываниями являются, например, следующие:
1. число 28 четное и делится на 7;
2.число х меньше или равно 8;
3. если треугольник равнобедренный, то углы в нем при основании равны. Составные высказывания образуются из элементарных с помощью слов «и» («А и В»), «или» («И или В»), частицы «не» (не А) и некоторых других. Эти слова в математике называют логическими связками.
Вообще каждому высказыванию приписывают одно из двух значений И (истина), если оно истинно, и Л (ложь), если оно ложно. Значения И и Л называют значениями истинности высказывания. Если высказывание элементарное, то его значение истинности определяют по содержанию, опираясь на известные знания. А как быть, если высказывание составное? Как определить значение истинности такого высказывания? Здесь на помощь приходит форма высказывания.
Конъюнкцией двух высказываний А и В называют высказывание вида А и В, истинное, если оба высказывания истинны, и ложное, если хотя бы одно из них ложное.
Пример. Установим, истинно или ложно высказывание: 1). число 102 четное и делится на 9.
В этом случае составное высказывание имеет форму «А и В», где А - «Число 102 четное», а В - «Число 102 делится на 9». Легко видеть, что высказывание А истинное, а высказывание В ложное (число 102 не делится на 9, так как на 9 не делится сумма цифр в записи этого числа). Следовательно, и все предложение ложное.
Дезъюнкцией двух высказываний А или В называют высказывание вида А или В, ложное, если оба высказывания ложные и истинное во всех остальных случаях.
Пример. Установим, истинны ли высказывания: число 102 четное или делится на 3.
В этом случае составное высказывание имеет форму «А или В», где А -«Число 102 четное», В - «Число 102 делится на 3»
Видим, что высказывания А или В истинны, следовательно, данное высказывание истинно.
Импликацией двух высказываний АиВгазывается высказывание вида А=>В (если А то В), ложное только в одном случае, если А истинное, а В -ложное, во всех остальных случаях оно истинное.
Отрицанием высказывания А называется высказывание вида А, которое истинно, если высказывание А ложно, и ложно, когда А истинно.
План
Высказывания с внешним отрицанием.
Конъюнктивные высказывания.
Дизъюнктивные высказывания.
Строго-дизъюнктивные высказывания.
Высказывания об эквивалентности.
Импликативные высказывания.
Высказывания с внешним отрицанием.
Высказывание с внешним отрицанием - это высказывание (суждение), в котором утверждается отсутствие некоторой ситуации. Оно чаще всего выражается предложением, начинающимся словосочетанием “неверно, что...” или “неправильно, что...”. Внешнее отрицание обозначается символом “ù ”, называемым знаком отрицания. Этот знак определяется следующей таблицей истинности:
В высказываниях с внешним отрицанием отрицается ситуация в А. Например, если А: “Волга впадает в Черное море”, то ùА: “Неверно, что Волга впадает в Черное море”.
Конъюнктивные высказывания.
Конъюнктивными высказываниями являются такие, в которых утверждается одновременное наличие двух ситуаций. Конъюнктивные высказывания образуются из двух высказываний при помощи союзов “и”, “а”, “но”. Форма конъюнктивного высказывания: (А&В). Каждое из высказываний А и В может принимать как значение “истина”, так и значение “ложь”. Эти значения для краткости обозначаются буквами и, л . Таблица истинности для конъюнктивных высказываний имеет следующий вид:
В конъюнктивных высказываниях утверждается, что ситуация, описанная в А и в В имеют место одновременно. Примеры конъюнктивных высказываний: “Земля - планета, а Луна - спутник”; “Петров хорошо освоил логику, но Сидоров освоил логику плохо”; “На улице темно, и в аудитории горит свет”; “Петров всучил чиновнику взятку деньгами, а Сидоров - бутылкой”.
Дизъюнктивные высказывания.
Дизъюнктивные высказывания - это высказывания, в которых утверждается наличие по крайней мере одной из двух ситуаций, описанных в А и В. Дизъюнкция обозначается символом V и выражается в естественном языке союзом “или”.
Табличное определение знака дизъюнкции имеет следующий вид:
Пример дизъюнктивного высказывания: “Роман Сергеевич Иванов является преподавателем, или Роман Сергеевич Иванов является аспирантом”.
Строго-дизъюнктивные высказывания .
Строго-дизъюнктивными называются высказывания, в которых утверждается наличие ровно одной из двух ситуаций, описанных в А и В. Такие высказывания чаще всего осуществляются посредством предложений с союзом “или..., или...” (“либо..., либо...”). Строгая дизъюнкция обозначается символом V* (читается “либо..., либо...”).
Табличное определение знака строгой дизъюнкции имеет следующий вид:
Пример строго-дизъюнктивного высказывания: “Либо на улице солнечно, либо идет дождь”.
В двух предыдущих лекциях мы определили логические операции — отрицание, конъюнкцию, два вида дизъюнкции, импликацию и эквиваленцию. Рассмотрим некоторые задачи на применение определений логических связок. Это задачи, где требуется выяснить значение истинности одного составного высказывания, если известно значение истинности другого составного высказывания, а также задачи, где требуется определить, существуют ли простые высказывания, если известны истинностные значения некоторых составных высказываний, образованных из этих высказываний.
Определить значение истинности высказывания, используя значения истинности других высказываний
Задача 6.1. Известно, что высказывание $ \displaystyle AB$ ложно, а высказывание $ \displaystyle A \to B $ истинно. Определить значение истинности высказывания $ \displaystyle B \to A’ $, если известно, что его можно однозначно определить, используя эти данные.
Решение. Предположим, что это высказывание ложно:
$ \displaystyle B \to A’=0 $.
Почему мы предположили ложность, а не истинность данной импликации? Причина очень проста: импликация ложна только в одном случае. Если это предположение не будет противоречить условию задачи, то оно верно, так как значение истинности всякого высказывания — это ложь или истина. Согласно определению импликации, она ложна тогда и только тогда, когда посылка истинна, а заключение ложно:
$ \displaystyle B= 1$, $ \displaystyle A’=0 $.
В силу определения отрицания, оно ложно тогда и только тогда, когда само высказывание истинно:
$ \displaystyle A=1 $.
Но в этом случае, учитывая определения импликации и конъюнкции,
$ \displaystyle A \to B=1 $, $ \displaystyle A B=1 $.
Однако по условию задачи последнее высказывание имеет значение истинности «ложь». Получили противоречие. Значит, высказывание $ \displaystyle B \to A’ $ истинно.
Задачу можно решить и другим способом: используя условие, напрямую получить значение истинности импликации. Так как
$ \displaystyle AB=0 $,
то, согласно определению конъюнкции, возможны следующие варианты распределения истинностных значений высказываний $ \displaystyle A $ и $ \displaystyle B $:
1) $ \displaystyle A=B=0 $;
3) $ \displaystyle A=1 $, $ \displaystyle B=0 $.
Поскольку
$ \displaystyle A \to B=1 $,
то, согласно определению импликации, получаем, что значения истинности высказываний $ \displaystyle A $ и $ \displaystyle B $ могут быть такими:
1) $ \displaystyle A=B=0 $;
2) $ \displaystyle A=0 $, $ \displaystyle B=1 $;
3) $ \displaystyle A=B=1 $.
Условия $ \displaystyle A=1 $, $ \displaystyle B=0 $ и $ \displaystyle A=B=1 $ несовместимы, так как любое высказывание либо истинно, либо ложно. Остаются первые два варианта. Проверим их, используя определения импликации и отрицания:
1) $ \displaystyle B \to A’=0 \to 0’=0 \to 1=1 $;
2) $ \displaystyle B \to A’=1 \to 0’=1 \to 1 =1 $.
В обоих случаях высказывание $ \displaystyle B \to A’ $ имеет значение истинности «истина».
Очевидно, что первый способ решения настоящей задачи гораздо короче, чем второй.
Выяснить, достаточно ли данных, чтобы определить значение истинности высказывания
Задача 6.2. Пусть высказывание $ \displaystyle A \to B $ ложно. Достаточно ли этого, чтобы определить значение истинности высказывания $ \displaystyle (B \to (A \to C)) \vee (B’ \to C) $? Если достаточно, то указать это значение. Если не достаточно, то показать на примерах, что возможны оба истинностных значения.
Решение. Поскольку
$ \displaystyle A \to B=0 $,
то, согласно определению импликации,
$ \displaystyle A=1$, $ \displaystyle B=0 $.
Значит, импликация $ \displaystyle B \to (A \to C) $ истинна, так как её посылка ложна (какими бы ни были значения истинности высказываний $ \displaystyle A $ и $ \displaystyle C $). Следовательно, учитывая определение дизъюнкции, высказывание $ \displaystyle (B \to (A \to C)) \vee (B’ \to C) $ имеет значение истинности «истина».
Задача 6.3. Пусть известно, что высказывание $ \displaystyle AB $ истинно. Возможно ли, используя эти данные, определить значение истинности высказывания $ \displaystyle (AB) \to ((ABC’) \vee (A’BC))$ ? Если возможно, то указать это значение. В противном случае показать на примерах, что высказывание может быть как истинным, так и ложным.
Решение. Поскольку конъюнкция двух высказываний истинна тогда и только тогда, когда оба этих высказывания истинны, то
$ \displaystyle A=B=1 $.
Значит, импликация $ \displaystyle (AB) \to ((ABC’) \vee (A’BC))$ истинна, если её заключение истинно, и ложна в противном случае (в силу определения данной логической связки). Рассмотрим дизъюнкцию $ \displaystyle (ABC’) \vee (A’BC) $. Известно, что
$ \displaystyle A=B=1 $.
Тогда, согласно определению отрицания $ \displaystyle A’=0 $. Если $ \displaystyle C=0 $, то $ \displaystyle C’=1 $. Следовательно, согласно определению, конъюнкция $ \displaystyle ABC’ $ истинна, а конъюнкция $ \displaystyle A’BC $ ложна. Значит, дизъюнкция $ \displaystyle (ABC’) \vee (A’BC) $ истинна. Если $ \displaystyle C=1 $, то $ \displaystyle C’=0 $. Следовательно, высказывания $ \displaystyle ABC’ $ и $ \displaystyle A’BC $ ложны. Тогда и дизъюнкция $ \displaystyle (ABC’) \vee (A’BC) $ ложна. Итак, высказывание $ \displaystyle (AB) \to ((ABC’) \vee (A’BC))$ имеет значение истинности «ложь» при
$ \displaystyle C=1 $
и «истина» при
$ \displaystyle C=0 $.
Получается, что нельзя однозначно определить значение истинности высказывания, используя условия задачи. Здесь нужно подчеркнуть, что это не означает, что значение истинности вообще нельзя определить. Просто здесь не хватает данных для этого.
Выяснить, существуют ли высказывания с данными значениями истинности
Задача 6.4. Пусть высказывание $ \displaystyle A \vee B’ $ и $ \displaystyle B \to (A \vee C) $ имеет значение истинности «ложь», а высказывание $ \displaystyle C’ \to B’ $ имеет значение истинности «истина». Существуют ли такие высказывания $ \displaystyle A $, $ \displaystyle B$ и $ \displaystyle C $?
Решение. Дизъюнкция двух высказываний, в силу определения, ложна только в одном случае: если ложны оба этих высказывания. Значит,
$ \displaystyle A=B’=0 $.
Следовательно, учитывая определения отрицания,
$ \displaystyle B=1 $.
Рассмотрим импликацию
$ \displaystyle B \to (A \vee C) $.
По условию задачи она ложна. Это возможно тогда и только тогда, когда
$ \displaystyle B=1 $, $ \displaystyle A \vee C =0 $.
Значит, в силу определения дизъюнкции,
$ \displaystyle A=C=0 $.
Следовательно,
$ \displaystyle C’ \to B’=0′ \to 1’=1 \to 0=0 $.
Но, согласно условию задачи, данная импликация истинна. Получили противоречие. Это означает, что не существует высказываний, удовлетворяющим таким условиям.
Похожие статьи
