У меня быстродействующий компьютер или я не закончу проект вовремя и сдам экзамен
8
Информационно-логические основы построения ЭВМ
Что из предложенного является высказыванием?
Задание №1
1. Который час?
2. Целое число 1 есть наименьшее положительное число.
3. Если х=3, то х^2=6.
4. Берегись автомобиля!
5. Южная Дакота – северный штат.
6. Все четные числа делятся на 2?
7. Загрузите пакеты в машину.
8. Юпитер – ближайшая к солнцу планета.
9. Это утверждение не может быть истинным.
10. Не следует хранить компакт-диски в микроволновой печи.
PAGE
9
Информационно-логические основы построения ЭВМ
PAGE
Высказывания в символической форме
Задание №2
Пусть P, Q и R обозначают следующие высказывания:
P: Мой компьютер - быстродействующий
Q: Я окончу проект вовремя
R: Я сдам экзамен
Высказывание «У меня не быстродействующий компьютер или я закончу проект вовремя»,
записанное в символической форме будет иметь вид .
10
Информационно-логические основы построения ЭВМ
PAGE
Высказывания в символической форме
Задание №3
Пусть P, Q и R обозначают следующие высказывания:
P: Он купит компьютер.
Q: Он будет праздновать всю ночь.
R: Он выиграет лотерею.
Высказывание «Если он не купит компьютер, то и праздновать всю ночь не будет», записанное в
символической форме будет иметь вид .
19
Информационно-логические основы построения ЭВМ
Схемы на элементах логики.
Задание №4
Структурная формула для логической схемы имеет вид .
А
В
С
ИЛИ
ИЛИ
И
НЕ
НЕ
F
PAGE
20
Информационно-логические основы построения ЭВМ
PAGE
Логические операции с множествами.
Задание №5
Даны множества точек А, В и С, принадлежащих кругу, треугольнику или прямоугольнику
соответственно. Используя операции над множествами (объединения, пересечения, разности и
дополнения) опишите множество точек,
ограниченное выделенной областью
.
26
Информационно-логические основы построения ЭВМ
PAGE
Решение логических задач
Задание №6
Три клоуна Бим, Бам и Бом вышли на арену в красной, зеленой и синей рубашках. Их туфли
были тех же цветов. У Бима цвета рубашки и туфель совпадали. У Бома ни туфли, ни рубашка не
были красными. Бам был в зеленых туфлях, а в рубашке другого цвета. Как были одеты клоуны?
Использовать метод таблиц для решения логической задачи.
26
Информационно-логические основы построения ЭВМ
PAGE
Решение логических задач.
Задание №7
Имеются два сосуда — трехлитровый и пятилитровый. Нужно, пользуясь этими сосудами,
получить 1, 2, 3, 4, 5, 6, 7 и 8 литров воды. В нашем распоряжении водопроводный кран и
раковина, куда можно выливать воду.
Решить задачу методом блок-схем.
26
Информационно-логические основы построения ЭВМ
PAGE
Решение логических задач.
Задание №8
В чашке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что
вода и молоко не в чашке, сосуд с лимонадом стоит между кувшином и сосудом с квасом, в
банке не лимонад и не вода, а стакан стоит между сосудом с молоком и банкой. Вода
находится в .
34
Информационно-логические основы построения ЭВМ
PAGE
Триггеры.
Задание №9
Часто сигналы проходят через тракты, не обладающие одинаковой задержкой. Поэтому
сигналы попадают на входы схемы не одновременно, что вызывает ложное срабатывание
триггера – эффект «гонок». Чтобы этого не происходило, используют синхронные RS триггеры.
Смоделировать работу
однотактного синхронного RS триггера:
Смоделировать работу
двухтактного синхронного RS триггера:
2. Целое число 1 есть наименьшее положительное число.
3. Если х=3, то х^2=6.
4. Берегись автомобиля!
5. Южная Дакота – северный штат.
6. Все четные числа делятся на 2?
7. Загрузите пакеты в машину.
8. Юпитер – ближайшая к солнцу планета.
9. Это утверждение не может быть истинным.
10. Не следует хранить компакт-диски в микроволновой печи.
Пусть P, Q и R обозначают следующие высказывания:
P: Мой компьютер ‑ быстродействующий
Q: Я окончу проект вовремя
R: Я сдам экзамен
Высказывание «У меня не быстродействующий компьютер или я закончу проект вовремя», записанное в символической форме будет иметь вид .
Пусть P, Q и R обозначают следующие высказывания:
P: Он купит компьютер.
Q: Он будет праздновать всю ночь.
R: Он выиграет лотерею.
Высказывание «Если он не купит компьютер, то и праздновать всю ночь не будет», записанное в символической форме будет иметь вид .
Ответ: P̅Q̅
Структурная формула для логической схемы имеет вид .
Ответ: F=(
Даны множества точек А, В и С, принадлежащих кругу, треугольнику или прямоугольнику соответственно. Используя операции над множествами (объединения, пересечения, разности и дополнения) опишите множество точек, ограниченное выделенной областью .
Три клоуна Бим, Бам и Бом вышли на арену в красной, зеленой и синей рубашках. Их туфли были тех же цветов. У Бима цвета рубашки и туфель совпадали. У Бома ни туфли, ни рубашка не были красными. Бам был в зеленых туфлях, а в рубашке другого цвета. Как были одеты клоуны?
Использовать метод таблиц для решения логической задачи.
Ответ: 1)Бим - красная рубашка, красные туфли.
2)Бам - синия рубашка, зеленые туфли.
2)Бом - зеленая рубашка, синие туфли.
Имеются два сосуда — трехлитровый и пятилитровый. Нужно, пользуясь этими сосудами, получить 1, 2, 3, 4, 5, 6, 7 и 8 литров воды. В нашем распоряжении водопроводный кран и раковина, куда можно выливать воду.
Решить задачу методом блок-схем.
НБ — наполнить больший сосуд
НМ — наполнить меньший сосуд
ОБ — опорожнить больший сосуд, вылив воду в раковину
ОМ — опорожнить меньший сосуд, вылив воду в раковину
Б→М — перелить из большего в меньший, пока больший сосуд не опустеет или меньший сосуд не наполнится
М→Б — перелить из меньшего в больший, пока меньший сосуд не опустеет или больший сосуд не наполнится.
Б = 0 ? — посмотреть, пуст ли больший сосуд;
М = З ? — посмотреть, наполнен ли малый сосуд.
Последовательность получения литров в каждом сосуде, по данной схеме:
Большой сосуд 0 5 2 2 0 5 4 4 1 1 0 5 3 3 0 0
Малый сосуд 0 0 3 0 2 2 3 0 3 0 1 1 3 0 3 0
Так же чтобы получить 8 литров воды нужно заполнить оба сосуда одновременно.
В чашке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в чашке, сосуд с лимонадом стоит между кувшином и сосудом с квасом, в банке не лимонад и не вода, а стакан стоит между сосудом с молоком и банкой. Вода находится в .
Часто сигналы проходят через тракты, не обладающие одинаковой задержкой. Поэтому сигналы попадают на входы схемы не одновременно, что вызывает ложное срабатывание триггера – эффект «гонок». Чтобы этого не происходило, используют синхронные RS триггеры.
Смоделировать работу
однотактного синхронного RS триггера:
При С = ‘0’ на выходах обоих конъюнкторов устанавливается ‘0’, поэтому триггер остаётся в устойчивом состоянии.
При С =’1’ на выходы конъюкторов поступает информация со входов S и R, которая устанавливает триггер в соответствующее состояние.
Смоделировать работу
двухтактного синхронного RS триггера:
Подадим С =1. Триггер Т1 принимает информацию. При этом на входе С триггера Т2 логический С=0. По окончании входе С триггера Т1 – логический С=0. При этом на входе С триггера Т2, С=1. И, следовательно, триггер Т2 устанавливается в соответствующее состояние.
Тут вы можете оставить комментарий к выбранному абзацу или сообщить об ошибке.
стоять только два значения T или F, то всего различных таблиц будет 2 4 = 16 . Каждая таблица истинности определяет свою бинарную логическую операцию и для них, конечно, придуманы свои названия и обозначения. Но мы на них останавливаться не будем, поскольку для конструирования любого сложного выражения нам всегда будет достаточно несколько из выше приведенных логических операций.
Рассмотрим вопрос о минимальном количестве логических связок, необходимых для представления любого высказывания, образованного с помощью определенных нами выше логических связок. Известно, что p q
можно выразить как ( p q ) ( q p ) , так что использовать операцию
необходимости использовать , если применяется ~ и . Кроме того, p q эквивалентно ~ ( ~ p ~ q ) и p q эквивалентно ~ ( ~ p ~ q ) . Проверка
того, что оставшиеся логические операции, соответствующие не рассмотренным таблицам истинности, могут быть получены с использованием связок ~ и или ~ и выполняется аналогично. Таким образом, любое высказывание может быть выражено через пару связок ~ и или ~ и , причем в любом случае необходимы обе связки. Однако существуют две связки, обладающие тем свойством, что любое высказывание может быть выражено с использованием только одной из них.
Эти связки: | — штрих Шеффера и ↓ — стрелка Пирса. Этим связкам соответствуют таблицы истинности
Для того чтобы показать, что любую связку можно заменить связкой |, достаточно показать это для пар связок ~ и или ~ и , поскольку возможность выразить любую связку одной из этих пар уже показана. Эквивалентность p | p и ~р устанавливается при помощи следующей
Точно так же таблица
показывает, что ( p | p ) | ( q | q ) эквивалентно p q . Можно также показать, что ( p | q ) | ( p | q ) эквивалентно p q .
Таким образом, проверив, что ~ и или ~ и можно выразить, используя только |, тогда и любую связку можно выразить, используя лишь |.
Проверьте самостоятельно, что
p ↓ p эквивалентно ~p , ( p ↓ p ) ↓ ( q ↓ q )
эквивалентно p q ,
а ( p ↓ q ) ↓ ( p ↓ q )
p q . Заметим, что
p | q эквивалентно
связка | называется не - и , а связка ↓ называется не - или .
Допустим, что задана произвольная таблица истинности. Существует простой способ найти высказывание, которому она соответствует. Например, предположим, что имеется таблица истинности
Известно, что p q истинно в случае 1 и ложно во всех остальных случаях. Аналогично, p ~ q истинно только в случае 2, ~ p q истинно только в случае 3, а ~ p ~ q истинно только в случае 4. Указанное в примере
высказывание должно быть истинным в случаях 1, 2 и 4. Возьмем высказывания, истинные только в этих случаях, и соединим их связкой или . Тогда мы получим высказывание, истинное только в требуемых случаях (строках). В нашем случае рассматриваемая таблица истинности
( p q ) ( p ~ q ) ( ~ p ~ q )
Конечно, полученная форма высказывания не является простейшей. Используя законы логики, почти всегда можно получить более короткую запись.
В случае таблиц истинности с тремя переменными имеем аналогичную ситуацию. Для каждой строки следующей таблицы приведено высказывание, истинное только для этой строки.
Если требуется построить высказывание, соответствующее конкретной таблице истинности, необходимо выбрать выражения, соответствующие
случаям (строкам), где высказывание истинно, и соединить их связкой
Упражнения.
Упражнения к п. 1.1 .
1. Среди приведенных ниже предложений найдите высказывания. Укажите их истинностные значения.
b) Число 1 есть наименьшее положительное целое число .
c) Если х = 3, то х 2 = 6 .
d) Берегись автомобиля!
e) Симферополь – южный город .
f) Все четные числа делятся на 2 .
g) Положите деньги в карман .
h) Земля — ближайшая к солнцу планета .
i) Не следует хранить компакт-диски в микроволновой печи .
2. Пусть р , q и r обозначают следующие высказывания:
р : Поездка в Париж является дорогостоящей , q : Я совершу поездку в Париж ,
r : У меня есть деньги .
Запишите в символической форме такие высказывания:
У меня нет денег и я не совершу поездку в Париж.
У меня нет денег и поездка в Париж является дорогостоящей или я совершу поездку в Париж .
Неверно, что у меня есть деньги и я поеду в Париж .
Поездка в Париж не является дорогостоящей и я поеду в Париж или поездка в Париж является дорогостоящей и я не поеду в Париж .
3. Пусть р , q и r обозначают следующие высказывания:
р : Мой компьютер — быстродействующий ,
q : Я окончу писать программу вовремя , r : Я сдам зачет .
Запишите в символической форме такие высказывания:
У меня не быстродействующий компьютер или я закончу писать программу вовремя.
Я не закончу писать программу вовремя и не сдам зачет . Неверно, что я закончу писать программу вовремя и сдам зачет .
У меня быстродействующий компьютер или я не закончу писать программу вовремя и сдам зачет .
4. Постройте таблицы истинности для каждого высказывания в упражнениях 2 и 3.
5. Пусть р , q и r обозначают следующие высказывания:
р : Эта игра очень трудна ,
q : Я играю в шахматы ,
r : Игра в шахматы требует времени .
Интерпретируйте следующие выражения как обычные высказывания:
6. Пусть р , q и r обозначают следующие высказывания:
р : Доги — большие собаки , q : У меня маленький дом , r : У меня есть дог .
Представьте следующие символические выражения как обычные высказывания
7. Постройте таблицы истинности для каждого высказывания в упражнениях
8. Постройте таблицы истинности для следующих высказываний:
Упражнения к п. 1.2
1. Пусть р, q и r обозначают следующие высказывания:
р : Он купит компьютер ,
q : Он будет праздновать всю ночь , r : Он выиграет в лотерею .
Запишите следующие высказывания в виде символических выражений:
а) Если он выиграет в лотерею, он купит компьютер и будет праздновать всю ночь .
б) Если он не купит компьютер, то и праздновать всю ночь не будет .
в) Если он выиграет в лотерею, то будет праздновать всю ночь и если он не выиграет в лотерею, то не купит компьютер .
г) Если он не выиграет в лотерею или не купит компьютер, то праздновать всю ночь не будет .
2. Пусть р, q и r обозначают следующие высказывания:
р : Он читает комиксы.
q : Он любит научную фантастику . r : Он — ученый - информатик .
Запишите следующие высказывания в виде символических выражений:
а) Если он читает комиксы и любит научную фантастику, то он — ученый - информатик .
б) Если он не читает комиксы и не любит научную фантастику, то он не является ученым - информатиком .
в) Если он читает комиксы, то он любит научную фантастику и если он не читает комиксы, то он — ученый - информатик .
г) Если он — ученый - информатик, то он читает комиксы или он не любит научную фантастику .
3. Пусть р, q и r обозначают следующие высказывания:
q : Он популярен ,
Запишите следующие символические выражения как высказывания:
4. Постройте таблицы истинности для следующих выражений:
5. Постройте таблицы истинности для следующих выражений:
6. Укажите, какие из следующих высказываний являются истинными:
7. Запишите в символическом виде высказывания:
а) Сейчас январь, но сейчас зима тогда и только тогда, когда мы находимся в северном полушарии .
б) Сейчас январь и сейчас зима в том и только том случае, если мы находимся в северном полушарии .
Ответ: а) p ( q r ) ; б) ( p q ) r , где
p: Сейчас январь ;
r: Мы находимся в северном полушарии
Упражнения к п. 1.3
1. Приведите следующие высказывания к виду p q или q p :
а) Он добьется успеха, только если будет усердно работать . б) Он счастлив, только если управляет автомобилем .
в) Наличия денег достаточно, чтобы быть счастливым . г) Наличие денег необходимо, чтобы быть счастливым .
д) Чтобы победить на выборах, нужно набрать достаточно голосов .
а) Пусть p: Он добьется успеха ; q: Он будет усердно работать , то высказывание если р, то q (т.е. p q ) примет вид: Если он добивается
успеха, то он работает усердно.
б) Пусть p: Он управляет автомобилем ; q: Он счастлив , то высказывание q только если р (т.е. q p ) примет вид: Если он счастлив, то он
в) Пусть p: У него есть деньги ; q: Он счастлив , то высказывание р достаточно для q (т.е. p q ) примет вид: Если у него есть деньги, он
г) Пусть p: У него есть деньги ; q: Он счастлив , то высказывание р необходимо для q (т.е. q p ) примет вид: Если он счастлив, то у него
д) Пусть p: Он победит на выборах ; q: Он получит достаточное количество голосов , то высказывание q необходимо для р , или если р, то q (т.е. p q ) может быть записано в виде Если он победит на
выборах, то он получит достаточное количество голосов.
2. Используя таблицы истинности, докажите следующие эквивалентности: а) Закон де Моргана
б) Свойство ассоциативности связки V
в) Свойство дистрибутивности связки или относительно и
г) Эквивалентность импликации и высказывания со связкой или
3. Используя пункт (г) предыдущего упражнения, покажите, что отрицание для p q эквивалентно ~ ( p ~ q ) .
4. Докажите, что p q ≡ ~ q ~ p не используя непосредственно таблицы истинности.
5. Используя логически эквивалентные высказывания и не применяя непосредственно таблицы истинности, покажите, что
6. Используя таблицы истинности, докажите, что p q ≡/ q p .
7. Дано высказывание Если я голосую, то я хороший гражданин .
а) Сформулируйте конверсию этого выражения. б) Сформулируйте инверсию этого выражения.
 этом разделе рассматриваются таблицы истинности, знакомство с которыми будет для нас первым шагом в изучении логики. Далее мы увидим, что таблицы истинности являются также основным инструментом для определения других важных понятий дискретной математики. Логика, созданная как наука знаменитым Аристотелем (384 322 до н.э.), на протяжении столетий использовалась для развития многих областей знания, включая теологию, философию, математику. Она тот фундамент, на котором построено все здание математики. По сути, логика это наука о рассуждениях, которая позволяет определить истинность или ложность того или иного математического утверждения, исходя из совокупности первичных предположений, называемых аксиомами. Логика применяется также в информатике для построения компьютерных программ и доказательства их корректности. Понятия, методы и средства логики лежат в основе современных информационных технологий. Одна из основных целей этой книги изложить основы математической логики, показать, как она используется в информатике, и разработать методы анализа и доказательства математических утверждений.
Высказывание это утверждение или повествовательное предложение, о котором можно сказать, что оно истинно или ложно. Иными словами, утверждение об истинности или ложности высказывания должно иметь смысл. Истинность или ложность, приписываемые некоторому утверждению, называются его значе-
нием истинности , èëè истинностным значением .
Вот примеры предложений, не являющихся высказываниями:
Прочтите эту главу до следующего занятия
(приказ или восклицание),
Это утверждение ложно
(внутренне противоречивое утверждение).
16 ГЛАВА 1. Таблицы истинности, логика, доказательства
Мы будем обозначать высказывания буквами латинского алфавита p, q, r, : : :
Например, p может обозначать утверждение Завтра будет дождь , а q утвер-
ждение Квадрат целого числа есть число положительное .
В обыденной речи для образования сложного предложения из простых используются связки особые части речи, соединяющие отдельные предложения. Наиболее часто употребляются связки è, èëè, íåò, åñëè : : : то, только если , è тогда и только тогда . В отличие от обыденной речи, в логике смысл таких связок должен быть определен однозначно. Истинность сложного высказывания однозначно определяется истинностью или ложностью составляющих его частей. Высказывание, не содержащее связок, называется простым . Высказывание, содержащее связки, называется сложным .
Пусть p и q обозначают высказывания
p : Джейн водит автомобиль ; q : У Боба русые волосы :
Джейн водит автомобиль и у Боба русые волосы
состоит из двух частей, объединенных связкой è . Это высказывание может быть символически записано в виде
где символ ^ обозначает слово è на языке символических выражений. Выражение p ^ q называется конъюнкцией высказываний p и q.
Точно так же высказывание
Джейн водит автомобиль или у Боба рыжие волосы .
символически выражается как
где _ обозначает слово èëè в переводе на символический язык. Выражение p _ q называется дизъюнкцией высказываний p и q.
Опровержение , èëè отрицание высказывания p обозначается через
Таким образом, если p есть высказывание Джейн водит автомобиль , òî p
это утверждение Джейн не водит автомобиль .
Если r есть высказывание Джо нравится информатика , òî Джейн не во-
дит автомобиль и у Боба русые волосы или Джо любит информатику символически запишется как (( p) ^ q) _ r: И наоборот, выражение p ^ ( q) ^ r это
РАЗДЕЛ 1.1. Высказывания и логические связки 17
символическая форма записи высказывания Джейн водит автомобиль, у Боба
волосы не русые и Джо нравится информатика .
Рассмотрим выражение p ^q. Если некто говорит: Джейн водит автомобиль и у Боба русые волосы , то мы, естественно, представляем себе Джейн за рулем автомобиля и русоволосого Боба. В любой другой ситуации (например, если Боб не русоволос или Джейн не водит автомобиль) мы скажем, что говорящий не прав.
Возможны четыре случая, которые нам необходимо рассмотреть. Высказывание p может быть истинным (T ) или ложным (F ) и независимо от того, какое истинностное значение принимает p, высказывание q может также быть истинным (T ) или ложным (F ). Таблица истинности перечисляет все возможные комбинации истинности и ложности сложных высказываний.
Ранее мы убедились, что только в первом случае высказывание p^q истинно. В остальных же мы имеем ложное значение p ^ q. Например, случай 3 описывает значение истинности для p ^ q, когда неверно, что Джейн водит автомобиль и у Боба русые волосы. Если p высказывание Джон богат , а q высказывание Джон красив , то не знакомая с Джоном девушка, которую убедили в том, что высказывание Джон богат и Джон красив , èëè Джон богат и красив истинно, будет представлять себе Джона и богатым, и красивым.
Точно так же рассмотрим высказывание
Джейн водит автомобиль или у Боба русые волосы ;
которое символически выражается как p _ q. Если некто скажет: Джейн водит автомобиль или у Боба русые волосы , то он будет не прав только тогда, когда Джейн не сможет управлять автомобилем, а Боб не будет русоволосым. Для того чтобы все высказывание было истинным, достаточно, чтобы одна из двух составляющих его компонент была истинной. Поэтому p _ q имеет таблицу истинности
Высказывание p _ q ложно только в случае 4, когда p и q оба ложны.
Если p высказывание Джон богат , а q высказывание Джон красив , и не знакомая с Джоном девушка уверена в истинности высказывания Джон богат или Джон красив , èëè Джон богат или красив , то она вправе ожидать, что
18 ГЛАВА 1. Таблицы истинности, логика, доказательства
истинно одно из высказываний, но не обязательно оба. Девушка почувствует себя введенной в заблуждение, только если обнаружит, что Джон беден и уродлив.
Таблица истинности для отрицания p имеет вид
Истинностное значение p всегда противоположно истинностному значе- нию p. В таблицах истинности отрицание всегда оценивается первым, если только за знаком отрицания не следует высказывание, заключенное в скобки. Поэтомуp _ q интерпретируется как ( p) _ q, так что отрицание применяется только к p. Если мы хотим отрицать все высказывание p^q, то это записывается как (p_q).
Символы ^ и _ называют бинарными связками, так как они связывают два высказывания как, например, в выражениях p ^ q и p _ q. Символ является унарной связкой, так как применяется только к одному высказыванию.
Еще одна бинарная связка это исключающее или , которое обозначается через _ . Высказывание p _ q истинно, когда истинно p или q, но не оба одновременно. Эта связка имеет таблицу истинности
Используя слово èëè , мы можем иметь в виду исключающее или . Например, когда мы говорим: Дик сдаст экзамен по логике или он не сдаст этот экзамен , мы, конечно, предполагаем, что Дик сделает что-то одно. Таким образом, когда мы говорим, что p либо истина, либо ложь, то, естественно, предполагаем, что это не выполняется одновременно. В логике исключающее или используется довольно редко, и в дальнейшем мы, как правило, будем обходиться без него.
Сэм уплатит налог за машину или Сэм утратит свою машину и будет ходить на работу пешком .
Пусть p обозначает высказывание Сэм уплатит налог за машину , q высказывание Сэм останется при своей машине , а r высказывание Сэм будет ходить на работу пешком . Тогда наше сложное высказывание можно представить в виде
где скобки использованы, чтобы показать, какие именно высказывания являются компонентами каждой связки.
Таблица истинности дает возможность однозначно указать те ситуации, когда высказывание p _ (( q) ^ r) является истинным; при этом мы должны быть
РАЗДЕЛ 1.1. Высказывания и логические связки 19
уверены, что учтены все случаи. Поскольку сложное высказывание содержит три основных высказывания p; q и r, то возможны восемь случаев
При нахождении значений истинности для столбца ( q) ^ r мы используем столбцы для ( q) и r, а также таблицу истинности для ^. Таблица истинности для ^ показывает, что высказывание ( q) ^ r истинно лишь в том случае, когда истинны оба высказывания ( q) и r. Это имеет место лишь в случаях 3 и 7.
Заметим, что при определении значений истинности для столбца p_(( q)^r) играет роль только истинность высказываний p и ( q) ^ r. Таблица истинности для _ показывает, что единственный случай, когда высказывание, образованное с помощью связки èëè , ложно, это случай, когда ложны обе части этого высказывания. Такая ситуация имеет место только в случаях 5, 6 и 8.
Если Сэм не уплатит налог за машину (т.e. p ложно, или имеет значение F ), лишится своей машины (q имеет значение F ) и будет ходить на работу пешком (r имеет значение T ), то будет иметь место случай 7. Тот, кто скажет: Сэм уплатит налог за машину или Сэм утратит машину и будет ходить на работу пешком , будет абсолютно прав.
Другой, эквивалентный способ построения таблицы истинности состоит в том, чтобы записывать истинностные значения выражения под связкой. Снова рассмотрим выражение p _ (( q) ^ r). Сначала мы записываем истинностные зна- чения под переменными p, q и r. Единицы под столбцами истинностных значений указывают на то, что этим столбцам истинностные значения присваиваются в первую очередь. В общем случае число под столбцом будет показывать номер шага, на котором производятся вычисления соответствующих истинностных значений.
20 ГЛАВА 1. Таблицы истинности, логика, доказательства
Затем мы записываем под символом истинностные значения высказывания q.
Далее записываем истинностные значения ( q) ^ r под символом ^.
Наконец, записываем значения высказывания p _ (( q) ^ r) под символом _.
ПРИМЕР 1.1. Пусть p, q и r обозначают, соответственно, высказывания Фрэд любит футбол , Фрэд любит гольф , Фрэд любит теннис . Требуется записать высказывание Фрэд любит футбол и неверно, что он любит гольф или теннис
в символической форме и указать соответствующую ему таблицу истинности.
РАЗДЕЛ 1.1. Высказывания и логические связки 21
Сначала заменим это высказывание эквивалентным Фрэду нравится футбол и неверно, что Фрэд любит гольф или теннис . Высказывание Фрэд любит гольф или теннис в символической форме записывается как q _ r. Высказывание Неверно, что Фрэд любит гольф или теннис , символически записывается как (q _ r), поскольку отрицание применяется ко всему высказыванию, которое следует после что . Итак, исходное высказывание символически изображается p ^ ( (q _ r)). Таблица истинности этого высказывания имеет вид
1. Найдите среди указанных ниже предложений высказывания. Укажите их истинностные значения.
á) Целое число 1 есть наименьшее положительное целое число. â) Åñëè x = 3, òî x 2 = 6.
ã) Берегись автомобиля!
ä) Южная Дакота южный штат.
2. Найдите среди указанных ниже предложений высказывания. Укажите их истинностные значения.
à) Все четные числа делятся на 2.
á) Загрузите пакеты в машину.
â) Это утверждение не может быть истинным. ã) Юпитер ближайшая к солнцу планета.
ä) Не следует хранить компакт-диски в микроволновой печи. 3. Пусть p, q и r обозначают следующие высказывания:
p : Путешествие на Марс является дорогостоящим. q : Я совершу путешествие на Марс.
r : У меня есть деньги.
Запишите в символической форме такие высказывания:
à) У меня нет денег и я не совершу путешествие на Марс .
á) У меня нет денег и путешествие на Марс является дорогостоящим или я совершу путешествие на Марс .
22 ГЛАВА 1. Таблицы истинности, логика, доказательства
â) Неверно, что у меня есть деньги и я полечу на Марс .
ã) Путешествие на Марс не является дорогостоящим и я полечу на Марс или путешествие на Марс является дорогостоящим и я не полечу на Марс .
4. Пусть p, q и r обозначают следующие высказывания: p : Мой компьютер быстродействующий.
q : Я окончу проект вовремя. r : Я сдам экзамен.
Запишите в символической форме такие высказывания:
à) У меня не быстродействующий компьютер или я закончу проект вовремя .
á) Я не закончу проект вовремя и не сдам экзамен . â) Неверно, что я закончу проект и сдам экзамен .
ã) У меня быстродействующий компьютер или я не закончу проект вовремя и сдам экзамен .
5. Постройте таблицы истинности для каждого высказывания в упражнении 3.
6. Постройте таблицы истинности для каждого высказывания в упражнении 4.
7. Пусть p, q и r обозначают следующие высказывания:
p : Эта игра очень трудна . q : Я играю в шахматы .
r : Игра в шахматы требует времени .
Интерпретируйте следующие выражения как обычные высказывания:
â) (p _ r) ^ q; ã) p ^ q ^ r.
8. Пусть p, q и r обозначают следующие высказывания: p : Доги большие собаки.
q : У меня маленький дом.
r : Ó ìåíÿ åñòü äîã.
Представьте следующие символические выражения как обычные высказывания:
á) p ^ ( q _ r); â) (p _ q) ^ r;
9. Постройте таблицы истинности для высказываний в упражнении 7.
10. Постройте таблицы истинности для высказываний в упражнении 8.
11. Постройте таблицы истинности для следующих высказываний:
á) (q ^ r) _ ( p ^ r); â) (p ^ r) _ ( q ^ r); ã) ( p _ (q ^ r)); ä) (p ^ r) _ (p ^ q).
РАЗДЕЛ 1.2. Условные высказывания 23
12. Постройте таблицы истинности для следующих высказываний:
á) ( q ^ r) _ (p ^ r); â) ((p ^ r) _ q);
1.2. УСЛОВНЫЕ ВЫСКАЗЫВАНИЯ
Допустим, некто утверждает, что если случится одно событие, то случится и другое. Это утверждение зачастую принимает форму угрозы, но мы рассмотрим более позитивный пример. Предположим, отец говорит сыну: Если в этом семестре ты сдашь все экзамены на ¾отлично¿, я куплю тебе машину . Заметьте, что высказывание имеет вид: åñëè p , òî q, где p высказывание В этом семестре ты сдашь все экзамены на ¾отлично¿ , а q высказывание Я куплю тебе машину . Сложное высказывание мы обозначим символически через p ! q. Спрашивается, при каких условиях отец говорит правду? Предположим, высказывания p и q истинны. В этом случае счастливый студент получает отличные оценки по всем предметам, и приятно удивленный отец покупает ему машину. Естественно, ни у кого не вызывает сомнения тот факт, что высказывание отца было истинным. Однако существуют еще три других случая, которые необходимо рассмотреть. Допустим, студент действительно добился отличных результатов, а отец не купил ему машину. Самое мягкое, что можно сказать об отце в таком случае, это то, что он солгал. Следовательно, если p истинно, а q ложно, то p ! q ложно. Допустим теперь, что студент не получил положительные оценки, но отец тем не менее купил ему машину. В этом случае отец предстает очень щедрым, но его никак нельзя назвать лжецом. Следовательно, если p ложно и q истинно, то высказывание åñëè p , òî q (т.е. p ! q) истинно. Наконец, предположим, что студент не добился отличных результатов, и отец не купил ему машину. Поскольку студент не выполнил свою часть соглашения, отец тоже свободен от обязательств. Таким образом, если p и q ложны, то p ! q считается истинным. Итак, единственный случай, когда отец солгал, это когда он дал обещание и не выполнил его.
Ответ: (С ᴜB )\АᴜА\(СᴜВ)
Три клоуна Бим, Бам и Бом вышли на арену в красной, зеленой и синей рубашках. Их туфли были тех же цветов. У Бима цвета рубашки и туфель совпадали. У Бома ни туфли, ни рубашка не были красными. Бам был в зеленых туфлях, а в рубашке другого цвета. Как были одеты клоуны?
Использовать метод таблиц для решения логической задачи.
Ответ: 1)Бим - красная рубашка, красные туфли.
2)Бам - синия рубашка, зеленые туфли.
2)Бом - зеленая рубашка, синие туфли.
Имеются два сосуда — трехлитровый и пятилитровый. Нужно, пользуясь этими сосудами, получить 1, 2, 3, 4, 5, 6, 7 и 8 литров воды. В нашем распоряжении водопроводный кран и раковина, куда можно выливать воду.
Решить задачу методом блок-схем.
НБ — наполнить больший сосуд
НМ — наполнить меньший сосуд
ОБ — опорожнить больший сосуд, вылив воду в раковину
ОМ — опорожнить меньший сосуд, вылив воду в раковину
Б→М — перелить из большего в меньший, пока больший сосуд не опустеет или меньший сосуд не наполнится
М→Б — перелить из меньшего в больший, пока меньший сосуд не опустеет или больший сосуд не наполнится.
Б = 0 ? — посмотреть, пуст ли больший сосуд;
М = З ? — посмотреть, наполнен ли малый сосуд.
Последовательность получения литров в каждом сосуде, по данной схеме:
Большой сосуд 0 5 2 2 0 5 4 4 1 1 0 5 3 3 0 0
Малый сосуд 0 0 3 0 2 2 3 0 3 0 1 1 3 0 3 0
Так же чтобы получить 8 литров воды нужно заполнить оба сосуда одновременно.
В чашке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в чашке, сосуд с лимонадом стоит между кувшином и сосудом с квасом, в банке не лимонад и не вода, а стакан стоит между сосудом с молоком и банкой. Вода находится в .
Часто сигналы проходят через тракты, не обладающие одинаковой задержкой. Поэтому сигналы попадают на входы схемы не одновременно, что вызывает ложное срабатывание триггера – эффект «гонок». Чтобы этого не происходило, используют синхронные RS триггеры.
Смоделировать работу
однотактного синхронного RS триггера:
При С = ‘0’ на выходах обоих конъюнкторов устанавливается ‘0’, поэтому триггер остаётся в устойчивом состоянии.
При С =’1’ на выходы конъюкторов поступает информация со входов S и R, которая устанавливает триггер в соответствующее состояние.
Смоделировать работу
двухтактного синхронного RS триггера:
Подадим С =1. Триггер Т1 принимает информацию. При этом на входе С триггера Т2 логический С=0. По окончании входе С триггера Т1 – логический С=0. При этом на входе С триггера Т2, С=1. И, следовательно, триггер Т2 устанавливается в соответствующее состояние.
Читайте также: