Задачи по логике

Задачи по логике с решением

 

Если у вас нету времени на задачи по логике вы всегда можете попросить меня, вам нужно написать мне, и я вам помогу онлайн или в срок 1-3 дня всё зависит что там у вас за работа, вдруг она огромная! Чуть ниже размещён теоретический и практический материал, который вам поможет сделать работу если у вас много свободного времени и желания!

 

Возможно, вас также заинтересует эта ссылка:

Заказать работу по логике помощь в учёбе

 

Высказывания и операции над ними. Под высказыванием мы понимаем предложение, представляющее собой такое утверждение, о котором можно судить, истинно оно или ложно. По совокупности всех высказываний определяется функция истинности, принимающая значения в двухэлементном множестве {0, 1}:

Значение называется логическим значением или значением истинности высказывания

Над высказываниями определяются следующие основные операции (логические связки), которые позволяют из имеющихся высказываний строить новые:

• 1) отрицание: (читается «не »);
• 2) конъюнкция: (читается « и », используется также иное обозначение: );
• 3) дизъюнкция: (читается « или »);
• 4) импликация: (читается «если , то », или «из следует », или « достаточно для », или « необходимо для »);
• 5) эквивалентность: (читается « равносильно », или « тогда и только тогда, когда », или « необходимо и достаточно для »).

При этом логические значения результатов этих операций связаны с логическими значениями исходных высказываний так, как указано в следующей таблице (таблице истинности соответствующих операций):

Каждую из этих операций можно рассматривать как операцию над символами 0 и 1. Так, например, дизъюнкция и импликация задают соответственно следующие правила действий с указанными символами:

 

Возможно, вас также заинтересует эта ссылка:

Решение задач по логике с примерами онлайн

 

 

Задача 1.1.

Какие из следующих предложений являются высказываниями:
а) Москва — столица России;
б) Студент механико-математического факультета университета;
в) Треугольник подобен треугольнику
г) Луна есть спутник Марса;
д) 2 + 2 - 5;
е) Кислород — газ;
ж) Каша — вкусное блюдо;
з) Математика — интересный предмет;
и) Картины Пикассо слишком абстрактны;
к) Железо тяжелее свинца;
л) «Да здравствуют музы!»;
м) Треугольник называется равносторонним, если все его стороны равны;
н) Если в треугольнике все углы равны, то он равносторонний;
о) Сегодня плохая погода;
п) В романе А. С. Пушкина «Евгений Онегин» 136 245 букв;
р) Река Ангара впадает в озеро Байкал.

• Решение:

б) Это предложение не является высказыванием, потому что оно ничего не утверждает о студенте.
в) Предложение не является высказыванием: мы не можем определить, истинно оно или ложно, потому что не знаем, о каких именно треугольниках идет речь. Фактически здесь является некоторой переменной, вместо которой могут подставляться конкретные значения (треугольники). О предложениях такого типа речь пойдет в в гл. 4.
ж) Предложение не является высказыванием, так как понятие «вкусное блюдо» слишком неопределенно.
п) Предложение — высказывание, но для выяснения его значения истинности нужно затратить немало времени.

 

Возможно, вас также заинтересует эта ссылка:

Контрольная работа по логике заказать

 

Задача 1.4.

Установите, какие из высказываний в следующих парах являются отрицаниями друг друга и какие нет (объясните почему):
а)
б)
в) «Треугольник прямоугольный», «Треугольник тупоугольный»;
г) «Натуральное число четно», «Натуральное число нечетно»;
д) «Функция нечетна», «Функция четна»;
е) «Все простые числа нечетны», «Все простые числа четны»;
ж) «Все простые числа нечетны», «Существует простое четное число»;
з) «Человеку известны все виды животных, обитающих на Земле», «На Земле существует вид животных, неизвестный человеку»;
и) «Существуют иррациональные числа», «Все числа — рациональные»;
к) «Если делится на 3, то делится на 9», «Если не делится на 3, то не делится на 9»;
л)

• Решение:

л) Высказывание не является отрицанием высказывания потому что требование не быть меньше оставляет две возможности: быть равным и быть больше . Таким образом, отрицанием высказывания является высказывание

 

Возможно, вас также заинтересует эта ссылка:

Помощь по логике онлайн

 

Задача 1.5.

Определите значения истинности следующих высказываний:
а) Санкт-Петербург расположен на Неве и 2 + 3 = 5;
б) 7 — простое число и 9 — простое число;
в) 7 — простое число или 9 — простое число;
г) Число 2 четное или это число простое;
д)
е) 2 - 2 = 4 или белые медведи живут е Африке;
ж) 2 - 2 = 4, и и
з) 2 — рациональное число или -5 — иррациональное число;
и) Фобос и Луна — спутники Марса;
к) У равнобедренного треугольника либо два, либо три угла равны между собой;
л) 3 - 3 = 9 и 4 + 7= 11.

• Решение:

л) Оба простых высказывания, к которым применяется операция конъюнкции, истинны, поэтому на основании определения этой операции и их конъюнкция есть истинное высказывание.

 

Возможно, вас также заинтересует эта ссылка:

Курсовая работа по логике заказать готовую онлайн

 

Задача 1.6.

Определите значения истинности высказываний если высказывания а)—д) истинны, а высказывания е)—л) ложны:

• Решение:

л) Конъюнкция высказываний есть ложное высказывание в случае, когда по меньшей мере одно из входящих в конъюнкцию составляющих высказываний (членов конъюнкции) ложно. В нашем случае второе составляющее высказывание истинно, а конъюнкция двух высказываний ложна. Поэтому первое составляющее высказывание ложно.

 

Возможно, вас также заинтересует эта ссылка:

РГР по логике расчетно графическая работа

 

Задача 1.7.

Сформулируйте и запишите в виде конъюнкции или дизъюнкции условие истинности каждого предложения ( — действительные числа):

• Решение:

л) Дробь равна нулю лишь в том случае, когда числитель равен нулю, а знаменатель отличен от нуля, т. е.

 

 

Задача 1.8.

Определите значения истинности высказываний если высказывания а)—д) ложны, а высказывания е)—л) истинны:
а) Если 4 — четное число, то
б) Если то 6 — четное число;
в) Если то
г) Если то
д) Если 6 — четное число, то
е) Если то 4 — нечетное число;
ж) Если то
з) Если то
и) Если 2 — четное число, то
к) Если 3 — четное число, то
л) Если 4 — четное число, то

• Решение:

л) Импликация двух высказываний есть ложное высказывание лишь в единственном случае, когда посылка истинна, а заключение ложно.

В данном случае посылка «4 — четное число» истинна, и по условию все высказывание также истинно. Поэтому заключение ложным быть не может, т.е. высказывание истинно.

 

 

Задача 1.9.

Определите значения истинности следующих высказываний:
а) Если 9 делится на 3, то 4 делится на 2;
б) Если 11 делится на 6, то 11 делится на 3;
в) Если 15 делится на 6, то 15 делится на 3;
г) Если 15 делится на 3, то 15 делится на 6;
д) Если Саратов расположен на Неве, то слоны — насекомые;
е) 12 делится на 6 тогда и только тогда, когда 12 делится на 3;
ж) 4 > 5 тогда и только тогда, когда -4 > -5;
з) 15 делится на 6 тогда и только тогда, когда 15 делится на 3;
и) 15 делится на 5 тогда и только тогда, когда 15 делится на 4;
к) Если 12 делится на 6, то 12 делится на 3;
л) 11 делится на 6 тогда и только тогда, когда 11 делится на 3.

• Решение:

к) Так как высказывание-посылка «12 делится на 6» истинно и высказывание-следствие «12 делится на 3» истинно, то и составное высказывание по определению импликации истинно.
л) Из определения эквивалентности видим, что высказывание вида истинно, если логические значения высказываний и совпадают, и ложно в противном случае. В данном примере оба высказывания, к которым применяется связка «тогда и только тогда», ложны. Поэтому все составное высказывание истинно.

 

 

Задача 1.13.

Пусть через обозначено высказывание «Это число — целое», через — высказывание «Это число положительное», через — высказывание «Это число простое», через — «Это число делится на 3». Прочитайте следующие высказывания:

• Решение:

л) Это число либо целое и простое, либо положи тельное и делящееся на 3.

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

Если — формула алгебры высказываний, содержащая пропозициональные переменные и некоторые конкретные высказывания, то, подставив последние в данную формулу вместо соответствующих пропозициональных переменных, получим составное высказывание

Логическое значение этого высказывания можно определить, если теперь вместо высказываний вставить символы их логических значений (0 или 1), а затем выполнить над этими символами последовательно все предписываемые формулой операции, т.е. Например, если
то логическое значение составного высказывания есть

В этом случае говорят, что формула принимает значение 0, если входящие в нее переменные принимают значения 1, 0, 1 соответственно.

Значок часто опускают. Это связано с тем, что в алгебре высказываний полностью отвлекаются от содержания высказываний, а изучают их только в связи с их свойством быть истинными или ложными. Поэтому каждое ложное высказывание можно рассматривать как элемент 0, а истинные — как элемент 1 и писать вместо или лишь только или (этим сокращением мы будем пользоваться, в частности, при составлении таблиц истинности формул).

 

• Формула называется выполнимой (опровержимой), если существует такой набор высказываний который обращает эту формулу в истинное (ложное) высказывание

Формула называется тождественно истинной, или тавтологией (тождественно ложной, или противоречием), если она обращается в истинное (ложное) высказывание при всех наборах значений переменных. Обозначение тавтологии:

 

 

Задача 1.22.

Определите, является ли последовательность символов формулой:

• Решение:

л) Данная последовательность не является формулой. В самом деле, пропозициональные переменные и согласно п. а) определения формулы являются формулами. Следовательно, согласно п. б) этого определения последовательность формулой не будет, так как входящие в нее формулы и не соединены ни одним из допустимых символов: и

Поэтому и данная последовательность формулой не является.

м) Согласно пп. а) и б) определения формулы пропозициональные переменные и выражения

 

 

Задача 1.24.

Выпишите всевозможные подформулы каждой из следующих формул (внешние скобки у формул опущены):

• Решение:

л) Подформула — это такая связная часть данной формулы, которая сама является формулой. Связность означает, что подформулу можно без разрыва «наложить» на данную формулу. Так, часть данной формулы таким свойством не обладает: чтобы «наложить» на данную формулу, ее нужно «разорвать» после знака Поэтому формула не является подформулой данной формулы. Подформулы удобно перечислять последовательно, по числу логических связок, занятых в ней. Во-первых, подформулами будут все пропозициональные переменные» входящие в данную формулу (это подформулы с нулевым числом логических связок): Далее, подформулы с одной логической связкой: Подформулы с двумя логическими связками: Подформулы с тремя логическими связками: Подформул с четырьмя логическими связками в данной формуле нет. Есть одна подформула с пятью связками: Наконец еще одна подформула совпадает с данной формулой. Таким образом, у данной формулы 12 подформул.
Тавтология алгебры высказываний. Решить задачи 1.28—1.33.

 

 

Задача 1.28.

Составив таблицы истинности следующих формул, докажите, что они являются тавтологиями:
а) (закон исключенного третьего);
б) (закон отрицания противоречия);
в) (закон двойного отрицания);
г) (закон тождества);
д) (закон контрапозиции);
е) (правило цепного заключения);
ж) (закон противоположности);
з) (коммутативность конъюнкции);
и) (коммутативность дизъюнкции);
к) (ассоциативность конъюнкции);
л) (ассоциативность дизъюнкции);
м) (дистрибутивность конъюнкции относительно дизъюнкции);
н) (дистрибутивность дизъюнкции относительно конъюнкции);
о) (идемпотентность конъюнкции);
п) (идемпотентность дизъюнкции);
Р)
с)
т) (первый закон поглощения);
У) (второй закон поглощения);

ф) (первый закон де Моргана);
х) (второй закон де Моргана);

ц)

• Решение:

д) Составим таблицу истинности данной формулы:

Таблица показывает, что, какого бы истинностного значения высказывания ни подставлялись в данную формулу вместо пропозициональных переменных и формула всегда превращается в истинное высказывание.
Значит, формула — тавтология.

 

 

Задача 1.32.

Докажите, что:

• Решение:

л) Пусть — формулы, о которых идет речь в задаче. Предположим, что формула не является тавтологией. Это означает, что существуют такие конкретные высказывания что высказывание ) истинно, а высказывание ложно. Тогда высказывание ложно. Далее, так как формула является тавтологией, то высказывание истинно. Но с другой стороны, поскольку — тавтология, то высказывание истинно. Получили противоречие. Следовательно, формула - тавтология.

м) Предположим, что посылка данного утверждения верна, а заключение нет, т.е. формулы являются тавтологиями, а формула — нет. Последнее означает: найдутся такие конкретные высказывания что высказывание будет ложным. Это, в свою очередь, возможно лишь в том случае, когда по меньшей мере одно из высказываний или будет ложным.

Высказывание ложным быть не может, поскольку это противоречило бы тождественной истинности формулы

Следовательно, ложно высказывание и, значит, истинно высказывание А раз так, то из истинности высказывания вытекает истинность высказывания
Обратимся теперь к высказыванию которое истинно, поскольку формула по предположению, является тавтологией. Ввиду истинности высказывания левая часть рассматриваемой эквивалентности есть ложное высказывание. Значит, ее правая часть, т.е. высказывание также ложна. Но это противоречит истинности этого высказывания, установленной в предыдущем абзаце.
Таким образом, сделанное допущение приводит в противоречию. Следовательно, допущение неверно, а верно доказываемое утверждение.

Логическое следование. Формула называется логическим следствием формул если она обращается в истинное высказывание на всяком наборе значений переменных, для которого в истинные высказывания обращаются все формулы Это обозначается:

 

 

 

Задача 1.34.

Формулы и от трех переменных заданы следующей таблицей истинностных значений:

Выясните, какие из формул являются логическими следствиями трех формул

• Решение:

11) Формула не является логическим следствием формул так как при все формулы принимают значение 1 (превращаются в истинные высказывания), а формула при этих значениях своих переменных принимает значение 0, т.е. превращается в ложное высказывание (см. строку 6 таблицы).

 

 

Задача 1.35.

Докажите, что справедливы следующие логические следования, руководствуясь определением этого понятия; выясните, будут ли верны обратные следования, т.е. будет ли формула, стоящая слева, логическим следствием формулы справа:

• Решение:

м) Составим сначала таблицу истинности для формулы стоящей слева от знака логического следования, и для формулы стоящей справа от этого знака:

Итак, логические значения данных формул представлены в столбцах построенной таблицы, отмеченных знаками () и () соответственно. Сравним теперь эти столбцы, руководствуясь определением логического следования (алгоритм см. в Учебнике, с. 55). Столбцы нужно сравнивать построчно, так как в каждой строке представлены значения двух формул, отвечающие одному и тому же набору значений пропозициональных переменных и входящих в эти формулы.

В первой строке столбца () стоит 1. Следовательно (на основании определения логического следования), мы должны посмотреть, стоит ли также 1 в первой строке столбца (), т.е. принимает ли значение 1 формула на том наборе значений пропозициональных переменных, на котором приняла значение 1 формула (в данной строке этот набор таков: Посмотрев на первую строку столбца (), мы убеждаемся, что в данном случае это действительно так.

Переходим ко второй строке. В ней в столбце () стоит 0. Определение логического следования в этом случае никаких требований к логическому значению второй формулы не предъявляет: ее значение в этой строке (т.е. при ) может быть
любым. Поэтому мы можем даже не смотреть, какое значение имеется во второй строке столбца ().
Переходим к третьей строке. В столбце () обнаруживаем также значение 0. Поэтому переходим к четвертой, заключительной, строке таблицы. В столбце () в этой строке — снова 0.

Таким образом, все строки таблицы просмотрены. Это означает, что мы сопоставили логические значения формул и при всевозможных наборах значений их пропозициональных переменных и обнаружили при этом, что на всяком наборе значений переменных, на котором первая формула принимает значение 1 (в нашем случае это лишь первая строка: в ней ), и вторая формула непременно принимает значение 1. По определению логического следствия это и означает, что формула является логическим следствием формулы

Дадим теперь ответ на второй вопрос, является ли формула логическим следствием формулы Посмотрим, например, во вторую строку построенной таблицы: в ней в столбце () стоит 1, а в столбце () — 0. Это означает, что формула при значениях переменных принимает значение 1, в то время как формула на том же наборе значений переменных принимает значение 0. Не глядя более ни в какие другие строки таблицы, на основании определения логического следствия заключаем, что формула не является логическим следствием формулы

• Заметим, что для данных формул имеется еще один набор значений переменных (это ), на котором «проваливается» определение логического следования формул (если говорить о следовании формулы В то же время на остальных наборах значений переменных определяющее свойство выполняется. Тем не менее достаточно одного «проваливающего» набора. Таким образом, формула не является логическим следствием формулы

Равносильность формул. Формулы и называются равносильными, или эквивалентными (обозначение: ), если при любых значениях переменных логические значения получающихся из формул и высказываний совпадают.

 

 

Задача 1.56.

Следующие формулы преобразуйте равносильным образом так, чтобы они содержали только логические связки

• Решение:

л) Проделаем требуемые равносильные преобразования:

 

 

Задача 1.58.

Следующие формулы преобразуйте равносильным образом так, чтобы они содержали только логические связки и

• Решение:

л) Проделаем равносильные преобразования:

 

 

 

Задача 1.70.

Упростите данную систему истинных высказываний, т.е. найдите логически эквивалентную ей систему, состоящую из меньшего числа не более сложных высказываний:

• Решение:

л) Упрощение совокупности высказываний основано на том, что каждое из высказываний данной совокупности будет истинным тогда и только тогда, когда истинна конъюнкция всех этих высказываний. Поэтому, составив конъюнкцию из данных высказываний и приведя ее равносильными преобразованиями к конъюнкции более простого вида, можно получить более простую систему высказываний, эквивалентную данной. В нашем случае имеем следующую конъюнкцию, которую последовательно упрощаем:

Следовательно, все высказывания данной системы будут истинны тогда и только тогда, когда будут истинны высказывания и Поэтому данная система трех высказываний оказалась логически эквивалентной более простой системе двух высказываний