Базовой курс информатики

имеет то преимущество
перед мозгом, что им пользуются

Габриэль Лауб

способах рассуждений и доказательств.
ПОНЯТИЕ — форма мышления, в которой

отражаются существенные признаки отдельного предмета или класса однородных предметов. Понятия в языке выражаются словами.

СУЖДЕНИЕ — это форма мышления, в которой что-либо утверждается или отрицается о предметах, признаках или их отношениях.

УМОЗАКЛЮЧЕНИЕ — форма мышления, посредством которой из одного или нескольких суждений, называемых посылками, мы по определенным правилам вывода получаем суждение-заключение.

Формы мышления

на хвойных деревья
Вода – жидкость
2 > 3

АЛГЕБРА ЛОГИКИ

(или Булева алгебра) оперирует с ЛОГИЧЕСКИМИ ПЕРЕМЕННЫМИ – высказываниями и суждениями (предикатами)

ВЫСКАЗЫВАНИЯ – это конкретные частные утверждения, о которых можно судить, истинно оно или ложно. В естественных языках высказывания выражаются повествовательными предложениями.

ПОНЯТИЕ ЛОГИЧЕСКИХ ПЕРЕМЕННЫХ

В
ы
С
К
А
З
ы
В
А
Н
И
Я

– четное число

Суждения становятся высказываниями, если переменным придать числовые значения

(пример: 3 – простое число).

Логические переменные могут принимать только два значения:
ИСТИННА - 1 или ЛОЖЬ – 0

СУЖДЕНИЯ (предикаты) – это утверждения о переменных.

ПОНЯТИЕ ЛОГИЧЕСКИХ ПЕРЕМЕННЫХ

С
У
ж
Д
Е
Н
И
Я

ли на свете человек, который мог объять необъятное?
Я земной шар

чуть не весь обошел!
Солнце есть спутник земли.
Если сумма квадратов двух сторон треугольника равна квадрату третьей, то он прямоугольный.
2+3=4
Сегодня отличная погода.
Железо – металл.
Если один угол в треугольнике прямой, то треугольник будет тупоугольным.
Который час?
Да здравствует 1 сентября!
Здесь нет высказываний.

ПОНЯТИЕ ЛОГИЧЕСКИХ ПЕРЕМЕННЫХ

переменной х
КВАНТОР ВСЕОБЩНОСТИ ∀ (все, всякий, каждый ).
Пример: Все следователи

– юристы. Все кошки являются рыбами.
ИСТИННОСТЬ ВЫСКАЗЫВАНИЯ С КВАНТОРОМ ОБЩНОСТИ УСТАНАВЛИВАЕТСЯ ПУТЕМ ДОКАЗАТЕЛЬСТВА, А ПОКАЗАТЬ ЛОЖНОСТЬ МОЖНО, ПРИВЕДЯ КОНТРПРИМЕР.
Выражение «существует х такое, что …» в логике называется квантором существования по переменной х
КВАНТОР СУЩЕСТВОВАНИЯ ∃(некоторые, существуют).
Пример: Некоторые следователи имеют высшее образование. Некоторые студенты – отличники.
ИСТИННОСТЬ ВЫСКАЗЫВАНИЯ С КВАНТОРОМ СУЩЕСТВОВАНИЯ УСТАНАВЛИВАЕТСЯ ПРИ ПОМОЩИ КОНТРЕКТНОГО ПРИМЕРА, А ЧТОБЫ УБЕДИТЬСЯ В ЛОЖНОСТИ НЕОБХОДИМО ПРОВЕСТИ ДОКАЗАТЕЛЬСТВО.

ЛОГИЧЕСКИЕ ОПЕРАЦИИ

К
В
А
Н
Т
О
Р
ы

Y – «На столе лежит карандаш»
Х∧Y – «На столе лежит

ручка и на
столе лежит карандаш»
 

Эта операция обозначается символами «∧» или «&».
В программировании эту операцию обозначают «AND».

КОНЪЮНКЦИЯ

Таблица истинности

Соединение двух логических переменных с помощью союза
«И» называется логическим умножением или КОНЪЮНКЦИЕЙ

ЛОГИЧЕСКИЕ ОПЕРАЦИИ

К
О
Н
Ъ
ю
Н
К
Ц
И
Я

библиотеке можно просмотреть журнал»
Х∨Y – «В библиотеке можно взять книгу

или
в библиотеке можно просмотреть журнал»

ДИЗЪЮНКЦИЯ

Эта операция обозначается символами «∨» или «+».
В программировании эту операцию обозначают «OR».

Таблица истинности

Соединение двух логических переменных с помощью союза
«ИЛИ» называется логическим сложением или ДИЗЪЮНКЦИЕЙ.

ЛОГИЧЕСКИЕ ОПЕРАЦИИ

Д
И
З
Ъ
ю
Н
К
Ц
И
Я

библиотеке можно просмотреть журнал»
Х⊕Y – «В библиотеке можно взять либо

книгу,
либо в библиотеке можно просмотреть журнал»

СТРОГАЯ ДИЗЪЮНКЦИЯ

Эта операция обозначается символами «∨» или «⊕».
В программировании эту операцию обозначают «ХOR».

Таблица истинности

Соединение двух логических переменных с помощью союза
«ЛИБО…ЛИБО» называется ИСКЛЮЧАЮЩИМ ИЛИ или СТРОГОЙ ДИЗЪЮНКЦИЕЙ.

.

ЛОГИЧЕСКИЕ ОПЕРАЦИИ

С
Т
Р
О
Г
А
Я

Д
И
З
Ъ
ю
Н
К
Ц
И
Я

программировании эту операцию обозначают «NOT».

Пример: Х – «Точка О является центром круга»
Инверсия: «Точка О не является центром круга»

Таблица истинности

ИНВЕРСИЯ

Присоединение частицы НЕ к логической переменной называется логическим отрицанием или ИНВЕРСИЕЙ.

ЛОГИЧЕСКИЕ ОПЕРАЦИИ

И
Н
В
Е
Р
С
И
Я

Y – «Треугольник равноугольный»
Х⇒Y – «Если треугольник равносторонний,

то он равноугольный»

Таблица истинности

ИМПЛИКАЦИЯ

Эта операция обозначается символами «→» или «⊃».
В программировании саму логическую операцию обозначают «IMP»,
а союз «если…,то…» заменяют связкой «IF…THEN…».

Соединение двух логических переменных с помощью союза «ЕСЛИ…, ТО…» называется логическим следованием или ИМПЛИКАЦИЕЙ.

 «Из лжи – все, что угодно».

ЛОГИЧЕСКИЕ ОПЕРАЦИИ

И
М
П
Л
И
К
А
Ц
И
Я

««Компьютер может производить вычисления тогда и только тогда, когда компьютер

включен»

ЭКВИВАЛЕНТНОСТЬ

Соединение двух логических переменных с помощью союза «…ТОГДА И ТОЛЬКО ТОГДА, КОГДА» называется логическим равенством или ЭКВИВАЛЕНТНОСТЬЮ.

Эта операция обозначается символами «≡» или «↔». В программировании саму логическую операцию обозначают «EQV».

Таблица истинности

ЛОГИЧЕСКИЕ ОПЕРАЦИИ

Э
К
В
И
В
А
Л
Е
Н
Т
Н
О
С
Т
Ь

скобки.

ЛОГИЧЕСКИЕ ОПЕРАЦИИ

они пересекаются.
б) Произведение равно нулю тогда и только тогда когда

один из множителей равен нулю.
в) Завтра я не пойду в школу.
г) Зимой мы обычно ходим на лыжах или катаемся на коньках на нашем пруду.
д) Я сделал домашнюю работу и получил за нее «пять».
е) Принтер либо устройство вывода информации, либо устройство хранения информации.
2. Постройте отрицания приведенных ниже высказываний:
а) водитель автомобиля не имеет права ехать на красный свет;
б) существует параллелограмм с прямым углом;
в) любое простое число нечетно;
г) на улице сухо;
д) в школу поставили новые компьютеры.

ЛОГИЧЕСКИЕ ОПЕРАЦИИ

•В∨С в) (В∧С)∨•А

Определите вид сложного высказывания, записав его структурной формулой

а) ни

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

ЛОГИЧЕСКИЕ ОПЕРАЦИИ

xn), аргументами которой являются логические переменные x1,x2,…, xn (простые высказывания).

Сама функция и аргументы могут принимать только два различных значения: «истина» (1) и «ложь» (0). Выше были рассмотрены функции двух аргументов: логическое умножение, логическое сложение, логическое отрицание, логическое равенство, логическое следование. Каждая логическое функция двух аргументов имеет четыре возможных набора значений аргументов. По формуле N=24=16 мы можем определить, какое количество различных логических функций двух аргументов может существовать. Таким образом, существует 16 различных логических функций двух аргументов, каждая из которых задается своей таблицей истинности.

эквивалентности, импликации, двойного отрицания, при этом знаки отрицания находятся только

при переменных.

1) закон тождества А=А
2) закон двойного отрицания (¬(¬A))=A
3) закон противоречия А ∧(¬А) = 0
4) закон исключения третьего А ∨(¬А) = 1
5) А→В= (¬А) ∨В
6) А↔В=(А ∧В) ∨((¬А) ∨ (¬В))
А↔В=((¬А) ∨ В) ∧ (А ∨ (¬В))
7) коммутативный закон: А∧В=В∧А
А∨В=В∨А
8) ассоциативный закон: ((А∧В)∧С)=(А∧(В∧С))
((А∨В) ∨С)=(А∨(В∨С))
9) дистрибутивный закон: (А∧(В∨С))=((А∧В) ∨ (А∧С))
(А∨(В∧С))=((А∨В) ∧ (А∨С))

11) закон идемпотентности: А∧А=А А∨А=А

12) законы исключения констант: А∧1=А А∨1=1
А∧0=0 А∨0=А
13) отрицание конъюнкций: ¬(А∧В) =(¬ А) ∨(¬ В)
14) отрицание дизъюнкций: ¬(А∨В) =(¬ А) ∧(¬ В)
15) закон исключения: (А∧В)∨((¬А)∧ В) = В
(А∨В)∧((¬А)∨В) = В

комнате сейчас находится какой-то человек или неверно,
что в соседней

комнате сейчас находится какой-то человек;
б) неверно, что на столе лежит ручка или на столе лежит карандаш;
в) завтра будет вьюга и будет дождь или завтра не будет вьюги и
будет дождь;
г) не является истинным, что Юра этого не делал.

ЗАКОНЫ ЛОГИКИ

обозначить их –
как принято –большими латинскими буквами.
Записать условие задачи

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

ЗАДАЧИ

((1∨0)∧(1∧1))∧(0∨1).
Даны два простых высказывания:
А={2·2=4}, В={2·2=5}.
Какие из составных высказываний истинны:
а) •А; б)

•В;
в) А∧В; г) А∨В;
д) А⇒В; е) А⇔В?
Даны простые высказывания:
А={Принтер – устройство ввода информации}
В={Процессор – устройство обработки информации}
С={Монитор – устройство хранения информации}
D={Клавиатура – устройство ввода информации}
Определите истинность составных высказываний:
а) (А∧В)∧(С∨D); б) (А∧В)⇒(В∧С);
В) (А∨В)⇔(С∧D); г) •А⇔•В.

ЗАДАЧИ

и 1000; в) 101010 и 111111.
Даны три числа в различных системах

счисления:
а) А=2010 , В=1116, С= 308.
Переведите А, В, С в двоичную систему счисления и выполните поразрядно логические операции (А∨В∧С). Ответ дайте в десятичной системе счисления.
Решение: 2010 = 101002 1116=100012 308 =110002

б) А=3010 , В=АF16, С= 568.

ЗАДАЧИ

3 и сумма делится на 3, то и другое слагаемое

делится на 3;
б) если одно слагаемое делится на 3,а другое слагаемое не делится
на 3, то сумма не делится на 3.
Формализуйте эти высказывания и составлением таблиц истинности
докажите, что полученные формулы эквивалентны.
Решение: Высказывание А - одно слагаемое делится на 3
Высказывание В - другое слагаемое делится на 3
Высказывание С - сумма делится на 3
F =А ∧ С ⇒ В ↔ А ∧•В ⇒•С

ЗАДАЧИ

или b=0), то a>0;
б) если a>b и a>0, то b>0

или b=0.
Формализуйте эти высказывания и составлением таблиц истинности
докажите, что полученные формулы эквивалентны.

Докажите с помощью таблиц истинности равносильность следующих
логических выражений:
а) (А⇒В)&(A∨•B)
б) (А⇔В)&(•A&•B)

ЗАДАЧИ

отнесен только к простым высказываниям:

а) ¬(A ∨ B) ∧•C =

•А∧•В ∧•C
б) ¬(•А∨В)
в) ¬( A ∧•B) ∨•C

Используя законы логики упростите выражения:

а) А∨(В∧А) = А ∨(А∧В) = А
б) С∨(А∧В)∨(•А∧В)
в) A∧(A∨B)∧(A∨C)
г) (A ∧B ∧ C) ∨(A ∧ B ∧•C)
д) (А ∨•А) ∧В

ЗАДАЧИ

не участвовал или Петров участвовал, то Сидоров участвовал;
Если Иванов не

участвовал, то Сидоров не участвовал.

Решение: F=•И∨П⇒С ∧ •И ⇒•С ответ: Иванов

ЗАДАЧИ

знавший ребят, высказал предположения:
Аня пойдет в кино только тогда, когда

пойдут Вика и Сергей;
Аня и Сергей пойдут в кино вместе или же оба останутся дома;
Чтобы Сергей пошел в кино, необходимо, чтобы пошла Вика.
Когда ребята пошли в кино, оказалось, что учитель немного ошибся: из трех его утверждений истинными оказались только два. Кто из ребят пошел в кино?
В нарушении правил обмена валюты подозреваются четыре работника банка – A, B, C, D. Известно, что:
Если А нарушил, то и В нарушил правила обмена валюты.
Если В нарушил, то и С нарушил или А не нарушал.
Если D не нарушал, то А нарушил, а С не нарушал.
Если D нарушил, то и А нарушил.
Кто из подозреваемых нарушил правила обмена валюты?

составляя различные расписания и во многих других случаях.
Среди задач, для

решения которых привлекается ЭВМ, немало таких, которые по традиции принято называть логическими. Кто не знает шуточной задачи о перевозке волка, козы и капусты с одного берега на другой! В такой задаче властвует не арифметика, а умение правильно рассуждать.
В жизни некоторые суждения и связи между ними бывают столь противоречивыми, что такие твердые логические орешки не под силу раскусить даже вдумчивому математику. Тогда на помощь в решении таких логических задач привлекают ЭВМ. Необходимо подчеркнуть, что умение использовать логические операции (AND, OR, NOT, EQV, IMP) повышают эффективность программирования. Именно формируя условия в операторе условной передачи управления (IF…THEN), программист использует логические операции.
В основе теории создания и работы дискретных преобразователей информации (вентили, сумматоры, триггеры и т.д.) лежат аппарат алгебры логики, сведения о двоичной арифметике и теории кодирования.  «Электронные мозги ошибаются гораздо точнее»
Габриэль Лауб

ЗАКЛЮЧЕНИЕ