Основы логики егэ информатика

Оглавление

Введение

Глава
1. Теоретический анализ раздела «Основы логики»

1.1.
Формы мышления. Алгебра высказываний.

1.2.
Логические выражения и функции

1.3.
Логические законы

1.4.
Базовые логические элементы

Глава
2. Методика подготовки к ЕГЭ по теме «Основы логики»

2.1.
Кодификатор

2.2.
Разбор заданий

2.3.
Основные трудности при решении заданий

2.4.
Анализ выполнения заданий этой темы

Глава
3. Решения задач ЕГЭ по теме «Основы логики»

Заключение

Список
литературы

Введение

Подготовка
к ЕГЭ по информатике стала актуальной с введением экзамена по информатике по
выбору при окончании средней школы и введением в некоторых ВУЗах, включая и
гуманитарные, вступительных экзаменов по информатике.

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

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

Предмет исследования
– методы подготовки к ЕГЭ по информатике по теме «Основы логики».

Объект исследования
– раздел «Основы логики» школьного курса информатики.

Цель: комплексное, системное
изучение методики подготовки к ЕГЭ по информатике по теме «Основы логики».

Достижение
поставленной цели требует постановки и решения следующих задач:

1.                
провести теоретический анализ раздела «Основы
логики»;

2.                
рассмотреть возможные трудности при
решении задач данной темы.

Глава 1. Теоретический анализ раздела
«Основы логики»

1.1. Формы мышления. Алгебра высказываний.

Логика
— наука о способах и формах мышления,  которая возникла в Древнем Китае и
Индии. 

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

Мышление
всегда осуществляется в следующих формах:  понятие, высказывание и
умозаключение. 

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

 В
алгебре высказываний простым высказываниям или  суждениям соответствуют логические
переменные.   Истинному высказыванию соответствует значение логической 
переменной 1, а ложному — значение 0. Над высказываниями  можно производить
определенные логические операции,  в результате которых получаются новые,
составные  высказывания[14, 98 c.].

Для
образования новых высказываний наиболее часто  используются базовые логические
операции, выражаемые  с помощью логических связок «и» (логическое умножение
(конъюнкция)), «или» (логическое сложение (дизъюнкция)), «не» (логическое
отрицание (инверсия)).

Конъюнкция. Операцию
логического умножения  (конъюнкцию) принято обозначать значком «&» либо «/»:

F
= А / В.

Функция
логического умножения F может принимать  лишь два значения «истина» (1) и
«ложь» (0). Значение логической функции определяется с помощью таблицы 
истинности:

Дизъюнкция. Операцию
логического сложения  обозначают «v» либо «+».

F
= A/B

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

Инверсия. Операцию
логического отрицания обозначают F = ¬A.

Таблица
истинности логического отрицания:

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

Логическое следование (импликация)
— это логическая функция, которую можно описать помощью оборота «если…,
то…», и обозначается:

А
–> В.

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

Логическое равенство (эквивалентность)
— это логическая функция, которую можно описать помощью оборота «тогда и только
тогда, когда …» и обозначается А<–>В.

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

1.2. Логические выражения и функции

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

Логические
операции выполняются в следующем порядке: инверсия, конъюнкция, дизъюнкция.
Скобки позволяют этот порядок изменить:

F
= (A/B) / (A/B)

Таблицу
истинности можно построить для каждого  логического выражения. Она определяет
его значение при всех возможных комбинациях значений логических переменных [14,
99 c.].

Построение
таблицы истинности:

1.                
Количество строк N в таблице истинности
равно количеству возможных комбинаций значений логических переменных n
и определяется по формуле: N = 2ⁿ.

2.                
Количество столбцов в таблице истинности
равно количеству логических переменных плюс количество логических операций.

3.                
Построить таблицу истинности с необходимым
количеством строк и столбцов и записать значения исходных логических
переменных.

4.                
Заполнить таблицу истинности по столбцам,
в соответствии с таблицами истинности.

1.3. Логические законы

Закон тождества.
Всякое высказывание тождественно  самому себе:

А
= А.

Закон непротиворечия.
Высказывание не может быть  одновременно истинным и ложным:

А
/ ¬А = 0.

Закон исключенного третьего.
Высказывание может быть либо истинным, либо ложным:

A
/ ¬A = 1.

Закон двойного отрицания.
Двойное отрицание дает в итоге исходное высказывание:

¬¬А
= А

Законы де Моргана:

¬(A
/ B)
= ¬A
/ ¬B

¬(A
/ B)
= ¬A
/ ¬B

Закон коммутативности.

А
/ В = В / А

A
/ B = B / A

Закон ассоциативности:

(А
/ В) / С = А / (В / С)

(A
/ B) / C = A / (B / C)

Закон дистрибутивности.
Отличается от подобного закона в алгебре — за скобки можно выносить не только
общие множители, но и общие слагаемые:

(A
/ B) / (A / C)=A / (B / C)

(A
/ B) / (A / C) = A / (B / C)

1.4. Базовые логические элементы

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

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

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

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

Из
тысяч и миллионов таких элементов строится ЭВМ [14, 103 c.].

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

0
+ 0 = 00

0
+ 1 = 01

1
+ 0 = 01

1
+ 1 = 10

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

Глава 2. Методика подготовки к ЕГЭ по
теме «Основы логики»

2.1. Кодификатор

Материал, проверяемый ЕГЭ

На
уровне воспроизведения знаний проверяется такой фундаментальный теоретический
материал, как: основные элементы математической логики.

Материал
на проверку сформированности умений применять свои знания в стандартной ситуации:

·                  
создавать и преобразовывать логические
выражения;

·                  
формировать для логической функции таблицу
истинности и логическую схему.

Материал
на проверку сформированности умений применять свои знания в новой ситуации:
решать логические задачи.

2.2. Разбор заданий

По
теме «Основы логики» в экзаменационной работе содержалось четыре задания: два с
выбором ответа и два с кратким ответом. Эти задания включали в себя проверку
умения строить таблицы истинности и логические схемы, преобразовывать
логические выражения, решение  логического уравнения. Уровень сложности,
максимальный первичный балл и время выполнения определяется по спецификации. Обозначения:
Б – базовый уровень сложности, П – повышенный уровень сложности, В – высокий
уровень сложности.

В
экзаменационных заданиях используются следующие соглашения:

1.
Обозначения для логических связок (операций):

a)                
отрицание (инверсия) обозначается ¬ (например,
¬А);

b)               
конъюнкция (логическое умножение,
логическое И) обозначается / (например, А / В);

c)                
дизъюнкция (логическое сложение,
логическое ИЛИ) обозначается / (например, A / В);

d)               
следование (импликация) обозначается –>
(например, А –> В);

e)                
символ 1 используется для обозначения
истины (истинного высказывания); символ 0 — для  обозначения лжи (ложного
высказывания).

2.
Два логических выражения, содержащих переменные, называются равносильными
(эквивалентными), если значения этих выражений совпадают при любых
значениях переменных. Так, выражения А –> В и (¬А) / В равносильны, а А /
В и А / В – нет (значения выражений разные, например, при А = 1, В = 0).

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

2.3. Основные трудности при решении заданий

Задание А10 повышенного уровня на
проверку знания основных понятий и законов математической логики. Задание А3 базового
уровня на умение строить таблицы истинности и логические
схемы, задания В12, повышенного уровня,  проверяют умение осуществлять
поиск информации в Интернет, используя логические операции. Задание В15
относится к высокому уровню сложности, требует от экзаменуемого умения
строить и преобразовывать логические выражения.

А3. Умение строить
таблицы истинности и логические схемы.

Типичные
ошибки:

·       серьезные сложности представляет применяемая в заданиях ЕГЭ форма
записи логических выражений с «закорючками», поэтому рекомендуется сначала внимательно
перевести их в «удобоваримый» вид;

·       расчет на то, что ученик перепутает значки Ù
и Ú (неверный ответ 1);

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

А10. Знание основных
понятий и законов математической логики.

Типичные
ошибки:

·      
можно «забыть» отрицание
(помните, что правильный ответ – всего один!);

·      
можно перепутать порядок
операций (скобки, «НЕ», «И», «ИЛИ», «импликация»);

·      
нужно помнить таблицу истинности
операции «импликация»;

·      
нужно помнить законы логики
(например, формулы де Моргана);

·      
при использовании формул де
Моргана нужно не забыть заменить «И» на «ИЛИ» и наоборот;

·      
нужно не забыть, например, что
инверсией (отрицанием) для выражения  X > 3 является X ≤ 3, а не X < 3;

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

В12. Умение осуществлять
поиск информации в Интернет.

Типичные
ошибки:

·   нужно внимательно читать условие, так как в некоторых задачах
требуется перечислить запросы в порядке убывания количества результатов, а в
некоторых – в порядке возрастания;

·   можно ошибиться в непривычных значках: «И» = &, «ИЛИ» = | (эти
обозначения привычны для тех, кто программирует на языке Си);

·   можно перепутать значение операций «И» и «ИЛИ», а также порядок
выполнения цепочки операций (сначала – «И», потом – «ИЛИ»);

·   для сложных запросов не всегда удастся так просто расположить
запросы по возрастанию (или убыванию) ограничений;

·   решение достаточно громоздко, хотя позволяет с помощью простых
операций решить задачу, не рискуя ошибиться при вычислениях «в уме» в сложных
случаях;

·   внимательнее с индексами переменных, очень легко по невнимательности
написать, например, N₅ вместо N₆ и получить совершенно другой результат.

В15. Умение строить и
преобразовывать логические выражения.

Типичные
ошибки:

·                  
Плохое знание таблиц истинности;

·                  
Ошибки из-за невнимательности к значкам,
которыми в выражениях обозначают логические операции. Это происходит от того,
что в разных учебниках эти значки отличаются по написанию;

·                  
нужно помнить правила
преобразования логических выражений и хорошо владеть этой техникой;

·                  
легко запутаться в
многочисленных столбцах с однородными данными (нулями и единицами);

·                  
длинное запутанное условие, из
которого нужно выделить действительно существенную информацию и формализовать
ее;

·                  
легко по невнимательности перепутать
порядок букв в ответе.

2.4. Анализ выполнения заданий этой темы

По
разделу «Основы логики» в экзаменационной работе содержится четыре задания: два
с выбором ответа и два с кратким ответом. Одно задание базового, два
повышенного и одно – высокого уровня сложности. Экзаменуемые хорошо справились
с заданием А3 базового уровня на проверку умения строить таблицы истинности и
логические схемы: 79% выполнения в среднем. Результат практически эквивалентен предыдущим
годам. Результат выполнения задания А10 повышенного уровня на проверку знания
основных понятий и законов математической логики также выше результатов прошлых
лет: 74% [2, 90 c.].

Как
и в прошлые годы задание В12 повышенного уровня сложности на умение
осуществлять поиск информации в Интернете с использованием логических операций дало
результат в среднем 51%. Результат выполнения задания В15 высокого уровня сложности
с кратким ответом на умение строить и преобразовывать логические выражения
составил 69%.

В
целом в 2013 году по теме «Основы логики» результаты полностью соответствуют и
иногда даже превосходят результаты, прогнозировавшиеся комиссией. Можно сделать
окончательный вывод о том, что повышенное внимание, уделенное этому разделу при
разборе результатов ЕГЭ предыдущих лет, дало свои плоды: результат усвоения
этой темы не выбивается из общего ряда.

Глава 3. Решения задач ЕГЭ по теме
«Основы логики»

А3. Символом
F
обозначено одно из указанных ниже логических выражений от трех аргументов: X,
Y,
Z.
Дан фрагмент таблицы истинности выражения F:

Какое выражение
соответствует F?

1) 
¬X Ù ¬Y Ù
¬Z        2)
X Ù Y Ù
Z         
 3) X Ù
¬Y Ù ¬Z            
4) X Ú
¬Y Ú ¬Z

Решение:

1)               
перепишем ответы в других
обозначениях:                  1)          2)       3)        4)

2)               
в столбце F есть единственная единица для
комбинации , простейшая функция, истинная (только)
для этого случая, имеет вид , она есть среди
приведенных ответов (ответ 3)

3)               
таким образом, правильный ответ – 3.

А 10.  На
числовой прямой даны два отрезка: P
=[10?30] и Q=[25,55]. Определите
наибольшую возможную длину отрезка A,
при котором формула (xÎA)→((xÎP)
Ú(xÎQ))
тождественна истинна, то есть принимает значение 1 при любом значении
переменной x.

1)   
10    2) 20   3) 30   4) 45

Решение:

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

A:  x Î
А,    P: x Î
P,     Q: x Î
Q

2)               
перейдем к более простым обозначениям

A
→ (P + Q)

3)               
раскроем импликацию через операции НЕ и
ИЛИ ():

4)               
для того, чтобы выражение было истинно при
всех x,  нужно, чтобы  было истинно там, где
ложно  (жёлтая область на рисунке)

5)               
поэтому максимальный отрезок, где A
может быть истинно (и, соответственно,  ложно)
– это отрезок [10,55], имеющий длину 45

6)               
Ответ: 4.

В12. В таблице приведены запросы и
количество страниц, которые нашел поисковый сервер по этим запросам в некотором
сегменте Интернета:

Сколько
страниц (в тысячах) будет найдено по запросу Рубин & Динамо &
Спартак?

Решение (вариант 1, круги Эйлера, полная диаграмма):

1)               
в этой задаче неполные данные, так как они
не позволяют определить размеры всех областей; однако их хватает для того,
чтобы ответить на поставленный вопрос

2)               
обозначим области, которые соответствуют
каждому запросу

3)               
из таблицы следует, что в суммарный
результат первых двух запросов область 2 входит дважды (1 + 2 + 2 + 3),
поэтому, сравнивая этот результат с третьим запросом (1 + 2 + 3), сразу находим
результат четвертого:

N₂
= (320 + 280) – 430 = 170

4)               
таким образом, ответ – 170.

В 15.
Сколько различных решений имеет система логических уравнений

(x₁®x₂)
® (x₃®x₄)=1

(x₃®x₄) ®
(x₅®x₆)=1

Где x₁,
x₂,…,x₆
– логические переменные? В ответе не нужно перечислять все различные наборы
значений переменных, при которых выполнено данное равенство. В качестве ответа
нужно указать количество таких наборов.

Решение (метод замены переменных):

1)               
используем замену переменных (заметим, что
каждая из новых переменных независима от других, это важно!):

Y₁
= x₁
® x₂,
       Y₂
= x₃
® x₄,
       Y₃
= x₅
® x₆

тогда система запишется в виде

Y₁ ®
Y­₂ = 1

Y₂ ®
Y­₃ = 1

2)               
можно объединить эти уравнения в одно

(Y₁ ®
Y­₂)
Ù (Y₂ ®
Y­₃)
= 1

для того, чтобы это равенство было
выполнено, ни одно из импликаций не должна быть ложной, то есть в битовой
цепочке, составленной из значений переменных  Y₁, Y­₂,
Y­₃,
не должно быть последовательности «10»; вот все возможные варианты:

3)               
теперь вернемся к исходным переменным;
импликация x₁
® x₂
дает 0 при одном наборе исходных переменных (x₁,x₂)
= (1,0) и 1 при трёх наборах  (x₁,x₂)
= {(0,0), (0,1), (1,1)}

4)               
учитывая, что каждая из новых переменных  Y₁,
Y­₂,
Y­₃,
независима от других; для каждой строки полученной таблицы просто перемножаем
количество вариантов комбинация исходных переменных:

5)               
складываем все результаты: 1 + 3 + 9 + 27
= 40

6)               
Ответ: 40.

Заключение

Тема
«Логика. Логические основы компьютера» – один из разделов, изучаемых в рамках
учебной дисциплины «Информатика и ИКТ» на профильном уровне.

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

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

В
работе представлены решения задач по теме «Основы логики», взятые из
демо-версий ЕГЭ по информатике разных лет.

Таким
образом, в результате проделанной работы были достигнута цель и решены
поставленные задачи.

Список литературы

1.                
Бочкин А. И. Методика преподавания
информатики. – Минск: Высшая школа, 2007. – 431 с.   

2.                
ЕГЭ 2013. Информатика.
Федеральный банк экзаменационных материалов / Авт.-сост. П. А. Якушкин, С. С.
Кры­лов. — М. : Эксмо, 2013. — 160 с.

3.                
Информатика : ЕГЭ-2013 : Самые
новые задания/авт.-сост. О.В. Ярцева, Е.Н. Цикина. — М.: ACT: Астрель, 2013. — 126 с.

4.                
Информатика и ИКТ: Учебник.
Начальный уровень / Под ред. Н. В. Макаровой. — СПб.: Питер, 2011.

5.                
Информатика и  ИКТ:  Учебник. 
8-9  класс  /  Под ред. Н. В. Макаровой. — СПб.: Питер, 2011.

6.                
Информатика и ИКТ: Практикум.
8-9 класс. / Под ред. Н. В. Макаровой. — СПб.: Питер, 2011.

7.                
Информатика и ИКТ: Учебник. 10
класс. Базовый уровень / Под ред. Н. В. Макаровой. — СПб.: Питер, 2011.

8.                
Информатика и ИКТ: Учебник. 11
класс. Базовый уровень / Под ред. Н. В. Макаровой — СПб.: Питер, 2011.

9.                
Информатика и ИКТ:
Методическое пособие для учителей. Т. 1. / Под ред. проф. Н. В. Макаровой. —
СПб.: Питер, 2011.

10.           
 Информатика и ИКТ: Методическое
пособие для учителей. Т. 2. / Под ред. проф. Н. В. Макаровой. СПб.: Питер, 2011.

11.           
 Информатика и ИКТ:
Методическое пособие для учителей. Т. 3. / Под ред. проф. Н. В. Макаровой.
СПб.: Питер, 2011.

12.           
 Лапчик М. П. и др. Методика
преподавания информатики.   – М.: Академия, 2011. – 624 с.

13.           
 Лыскова В. Ю., Ракитина Е. А.
Логика в информатике. – М.:   ЛБЗ, 2011. – 160 с.  

14.           
 Молодцов В.А.  Информатика :
тесты, задания, лучшие методики /  Молодцов В.А., Рыжикова Н.Б. — Ростов н/Д :
Феникс, 2008. — 217 с.

15.           
 Подготовка к ЕГЭ по
дисциплине «Информатика и ИКТ» / Под ред. Н. В. Макаровой. — СПб.: Питер, 2011.

16.           
 Семакин И. Г., Шеина Т. Ю.
Преподавание базового курса информатики в средней школе. Методическое пособие.
– М.: БИНОМ. ЛБЗ, 2012.

17.           
 Софронова Н. В. Теория и методика
обучения информатике.   – М.: Высшая школа, 2009. – 223 с.

Алгебра логики (англ. algebra of logic) — один из основных разделов математической логики, в котором методы алгебры используются в логических преобразованиях.

Основоположником алгебры логики является английский математик и логик Дж. Буль (1815–1864), положивший в основу своего логического учения аналогию между алгеброй и логикой. Любое высказывание он записывал с помощью символов разработанного им языка и получал «уравнения», истинность или ложность которых можно было доказать, исходя из определенных логических законов, таких как законы коммутативности, дистрибутивности, ассоциативности и др.

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

Логическое высказывание — это любое повествовательное предложение, в отношении которого можно однозначно утверждать, что его содержание истинно или ложно.

Например, «3 умножить на 3 равно 9», «Архангельск севернее Вологды» — истинные высказывания, а «Пять меньше трех», «Марс — звезда» — ложные.

Очевидно, что не всякое предложение может быть логическим высказыванием, т. к. не всегда есть смысл говорить о его ложности или истинности. Например, высказывание «Информатика — интересный предмет» неопределенно и требует дополнительных сведений, а высказывание «Для ученика 10-А класса Иванова А. А. информатика — интересный предмет» в зависимости от интересов Иванова А. А. может принимать значение «истина» или «ложь».

Кроме двузначной алгебры высказываний, в которой принимаются только два значения — «истинно» и «ложно», существует многозначная алгебра высказываний. В такой алгебре, кроме значений «истинно» и «ложно», употребляются такие истинностные значения, как «вероятно», «возможно», «невозможно» и т. д.

В алгебре логики различаются простые (элементарные) высказывания, обозначаемые латинскими буквами (A, B, C, D, …), и сложные (составные), составленные из нескольких простых с помощью логических связок, например таких, как «не», «и», «или», «тогда и только тогда», «если … то». Истинность или ложность получаемых таким образом сложных высказываний определяется значением простых высказываний.

Обозначим как А высказывание «Алгебра логики успешно применяется в теории электрических схем», а через В — «Алгебра логики применяется при синтезе релейно-контактных схем».

Тогда составное высказывание «Алгебра логики успешно применяется в теории электрических цепей и при синтезе релейно-контактных схем» можно кратко записать как А и В; здесь «и» — логическая связка. Очевидно, что поскольку элементарные высказывания А и В истинны, то истинно и составное высказывание А и В.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение.

Логических значений всего два: истина (TRUE) и ложь (FALSE). Это соответствует цифровому представлению — 1 и 0. Результаты каждой логической операции можно записать в виде таблицы. Такие таблицы называют таблицами истинности.

Основные операции алгебры логики

1. Логическое отрицание, инверсия (лат. inversion — переворачивание) — логическая операция, в результате которой из данного высказывания (например, А) получается новое высказывание (не А), которое называется отрицанием исходного высказывания, обозначается символически чертой сверху ($A↖{-}$) или такими условными обозначениями, как ¬, ‘not’, и читается: «не А», «А ложно», «неверно, что А», «отрицание А». Например, «Марс — планета Солнечной системы» (высказывание А); «Марс — не планета Солнечной системы» ($A↖{-}$); высказывание «10 — простое число» (высказывание В) ложно; высказывание «10 — не простое число» (высказывание B ) истинно.

Операция, используемая относительно одной величины, называется унарной. Таблица значений данной операции имеет вид

или

Высказывание $A↖{-}$ ложно, когда А истинно, и истинно, когда А ложно.

Геометрически отрицание можно представить следующим образом: если А — это некоторое множество точек, то $A↖{-}$ — это дополнение множества А, т. е. все точки, которые не принадлежат множеству А.

2. Конъюнкция (лат. conjunctio — соединение) — логическое умножение, операция, требующая как минимум двух логических величин (операндов) и соединяющая два или более высказываний при помощи связки «и» (например, «А и В»), которая символически обозначается с помощью знака ∧ (А ∧ В) и читается: «А и В». Для обозначения конъюнкции применяются также следующие знаки: А ∙ В; А & В, А and В, а иногда между высказываниями не ставится никакого знака: АВ. Пример логического умножения: «Этот треугольник равнобедренный и прямоугольный». Данное высказывание может быть истинным только в том случае, если выполняются оба условия, в противном случае высказывание ложно.

Таблица истинности операции имеет вид

или

Высказывание А ∧ В истинно только тогда, когда оба высказывания — А и В истинны.

Геометрически конъюнкцию можно представить следующим образом: если А, В — это некоторые множества точек, то А ∧ В есть пересечение множеств А и В.

3. Дизъюнкция (лат. disjunction — разделение) — логическое сложение, операция, соединяющая два или более высказываний при помощи связки «или» (например, «А или В»), которая символически обозначается с помощью знака ∨ (А ∨ В) и читается: «А или В». Для обозначения дизъюнкции применяются также следующие знаки: А + В; А or В; А | B. Пример логического сложения: «Число x делится на 3 или на 5». Это высказывание будет истинным, если выполняются оба условия или хотя бы одно из условий.

Таблица истинности операции имеет вид

или

Высказывание А ∨ В ложно только тогда, когда оба высказывания — А и В ложны.

Геометрически логическое сложение можно представить следующим образом: если А, В — это некоторые множества точек, то А ∨ В — это объединение множеств А и В, т. е. фигура, объединяющая и квадрат, и круг.

4. Дизъюнкция строго-разделительная, сложение по модулю два — логическая операция, соединяющая два высказывания при помощи связки «или», употребленной в исключающем смысле, которая символически обозначается с помощью знаков ∨ ∨ или ⊕ (А ∨ ∨ В, А ⊕ В) и читается: «либо А, либо В». Пример сложения по модулю два — высказывание «Этот треугольник тупоугольный или остроугольный». Высказывание истинно, если выполняется какое-то одно из условий.

Таблица истинности операции имеет вид

или

Высказывание А ⊕ В истинно только тогда, когда высказывания А и В имеют различные значения.

5. Импликация (лат. implisito — тесно связываю) — логическая операция, соединяющая два высказывания при помощи связки «если…, то» в сложное высказывание, которое символически обозначается с помощью знака → (А → В) и читается: «если А, то В», «А влечет В», «из А следует В», «А имплицирует В». Для обозначения импликации применяется также знак ⊃ (A ⊃ B). Пример импликации: «Если полученный четырехугольник квадрат, то около него можно описать окружность». Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием. Результат операции ложен только тогда, когда предпосылка есть истина, а следствие — ложь. Например, «Если 3 * 3 = 9 (А), то Солнце — планета (В)», результат импликации А → В — ложь.

Таблица истинности операции имеет вид

или

Для операции импликации справедливо утверждение, что из лжи может следовать все что угодно, а из истины — только истина.

6. Эквивалентность, двойная импликация, равнозначность (лат. aequalis — равный и valentis — имеющий силу) — логическая операция, позволяющая из двух высказываний А и В получить новое высказывание А ≡ В, которое читается: «А эквивалентно B». Для обозначения эквивалентности применяются также следующие знаки: ⇔, ∼. Эта операция может быть выражена связками «тогда и только тогда», «необходимо и достаточно», «равносильно». Примером эквивалентности является высказывание: «Треугольник будет прямоугольным тогда и только тогда, когда один из углов равен 90 градусам».

Таблица истинности операции эквивалентности имеет вид

или

Операция эквивалентности противоположна сложению по модулю два и имеет результат «истина» тогда и только тогда, когда значения переменных совпадают.

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

Приоритет выполнения логических операций следующий: отрицание («не») имеет самый высокий приоритет, затем выполняется конъюнкция («и»), после конъюнкции — дизъюнкция («или»).

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

Рассмотрим, например, построение составного высказывания из высказываний А и В, которое было бы ложно тогда и только тогда, когда оба высказывания истинны. В таблице истинности для операции сложения по модулю два находим: 1 ⊕ 1 = 0. А высказывание может быть, например, таким: «Этот мяч полностью красный или полностью синий». Следовательно, если утверждение А «Этот мяч полностью красный» — истина, и утверждение В «Этот мяч полностью синий» — истина, то составное утверждение — ложь, т. к. одновременно и красным, и синим мяч быть не может.

Примеры решения задач

Пример 1. Определить для указанных значений X значение логического высказывания ((X > 3) ∨ (X < 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

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

Отсюда получаем:

1) для X = 1:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) для X = 12:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) для X = 3:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

Пример 2. Указать множество целых значений X, для которых истинно выражение ¬((X > 2) → (X > 5)) .

Решение. Операция отрицания применена ко всему выражению ((X > 2) → (X > 5)) , следовательно, когда выражение ¬((X > 2) → (X > 5)) истинно, выражение ((X > 2) →(X > 5)) ложно. Поэтому необходимо определить, для каких значений X выражение ((X > 2) → (X > 5)) ложно. Операция импликации принимает значение «ложь» только в одном случае: когда из истины следует ложь. А это выполняется только для X = 3; X = 4; X = 5.

Пример 3. Для каких из приведенных слов ложно высказывание ¬(первая буква гласная ∧ третья буква гласная) ⇔ строка из 4 символов? 1) асса; 2) куку; 3) кукуруза; 4) ошибка; 5) силач.

Решение. Рассмотрим последовательно все предложенные слова:

1) для слова асса получим: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

2) для слова куку получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

3) для слова кукуруза получим: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 — высказывание ложно;

4) для слова ошибка получим: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 — высказывание истинно;

5) для слова силач получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 — высказывание ложно.

Построение таблиц истинности логических выражений

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

Удобной формой записи при нахождении значений функции является таблица, содержащая, кроме значений переменных и значений функции, также значения промежуточных вычислений. Рассмотрим пример построения таблицы истинности для формулы ${X1}↖{-} ∧ X2 ∨ {X1 ∨ X2}↖{-} ∨ X1$.

Если функция принимает значение 1 при всех наборах значений переменных, она является тождественно-истинной; если при всех наборах входных значений функция принимает значение 0, она является тождественно-ложной; если набор выходных значений содержит как 0, так и 1, функция называется выполнимой. Приведенный выше пример является примером тождественно-истинной функции.

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

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

Алгоритм построения ДНФ следующий:

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

Пример. Построить функцию, определяющую, что первое число равно второму, используя метод ДНФ. Таблица истинности функции имеет вид

Решение. Выбираем наборы значений аргументов, в которых функция равна 1. Это первая и четвертая строки таблицы (строку заголовка при нумерации не учитываем).

Записываем логические произведения аргументов этих наборов, объединив их логической суммой: X1 ∧ X2 ∨ X1 ∧ X2 .

Записываем отрицание относительно аргументов выбранных наборов, имеющих ложное значение (четвертая строка таблицы; второй набор в формуле; первый и второй элементы): X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

Ответ: F(X1, X2) = X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

2. Конъюнктивно нормальная форма (КНФ) — произведение сумм, образованных из переменных и их отрицаний для истинных значений.

Алгоритм построения КНФ следующий:

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

Примеры решения задач

Пример 1. Рассмотрим предыдущий пример, т. е. построим функцию, определяющую, что первое число равно второму, используя метод КНФ. Для заданной функции ее таблица истинности имеет вид

Решение. Выбираем наборы значений аргументов, в которых функция равна 0. Это вторая и третья строки (строку заголовка при нумерации не учитываем).

Записываем логические суммы аргументов этих наборов, объединив их логическим произведением: X1 ∨ X2 ∧ X1 ∨ X2 .

Записываем отрицание относительно аргументов выбранных наборов, имеющих истинное значение (вторая строка таблицы, первый набор формулы, второй элемент; для третьей строки, а это второй набор формулы, первый элемент): X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2.

Таким образом, получена запись логической функции в КНФ.

Ответ: X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2.

Полученные двумя методами значения функций являются эквивалентными. Для доказательства этого утверждения используем правила логики: F(X1, X2) = X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2 = X1 ∧ ${X1}↖{-}$ ∨ X1 ∧ X2 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ ${X2}↖{-}$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ 0 = X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

Пример 2. Построить логическую функцию для заданной таблицы истинности:

Решение. Используем алгоритм ДНФ для построения исходной функции:

Искомая формула: X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ X2 .

Ее можно упростить: X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ X2 = X2 ∧ (X1 ∨ ${X1}↖{-}$) = X2 ∧ 1 = X2.

Пример 3. Для приведенной таблицы истинности построить логическую функцию, используя метод ДНФ.

Искомая формула: X1 ∧ X2 ∧ X ∨ ${X1}↖{-}$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ ${X3}↖{-}$ ∪ X1 ∧ ${X2}↖{-}$ ∧ ${X3}↖{-}$.

Формула достаточно громоздка, и ее следует упростить:

X1 ∧ X2 ∧ X3 ∨ ${X1}↖{-}$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ ${X3}↖{-}$ ∨ X1 ∧ ${X2}↖{-}$ ∧ ${X3}↖{-}$ = X2 ∧ X3 ∧ (X1 ∨ ${X1}↖{-}$) ∨ X1 ∧ ${X3}↖{-}$ ∧ (X2 ∨ ${X2}↖{-}$) = X2 ∧ X3 ∨ X1 ∧ ${X3}↖{-}$.

Таблицы истинности для решения логических задач

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

Примеры решения задач

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

Решение. Очевидно, что результатом решения будет таблица, в которой искомая функция Y(X1, X2, X3) будет иметь значение «истина», если какие-либо две переменные имеют значение «истина».

Пример 2. Составить расписание уроков на день, учитывая, что урок информатики может быть только первым или вторым, урок математики — первым или третьим, а физики — вторым или третьим. Возможно ли составить расписание, удовлетворив всем требованиям? Сколько существует вариантов расписания?

Решение. Задача легко решается, если составить соответствующую таблицу:

Из таблицы видно, что существуют два варианта искомого расписания:

1. математика, информатика, физика;
2. информатика, физика, математика.

Пример 3. В спортивный лагерь приехали трое друзей — Петр, Борис и Алексей. Каждый из них увлекается двумя видами спорта. Известно, что таких видов спорта шесть: футбол, хоккей, лыжи, плавание, теннис, бадминтон. Также известно, что:

1. Борис — самый старший;
2. играющий в футбол младше играющего в хоккей;
3. играющие в футбол и хоккей и Петр живут в одном доме;
4. когда между лыжником и теннисистом возникает ссора, Борис мирит их;
5. Петр не умеет играть ни в теннис, ни в бадминтон.

Какими видами спорта увлекается каждый из мальчиков?

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

Так как видов спорта шесть, получается, что все мальчики увлекаются разными видами спорта.

Из условия 4 следует, что Борис не увлекается ни лыжами, ни теннисом, а из условий 3 и 5, что Петр не умеет играть в футбол, хоккей, теннис и бадминтон. Следовательно, любимые виды спорта Петра — лыжи и плавание. Занесем это в таблицу, а оставшиеся клетки столбцов «Лыжи» и «Плавание» заполним нулями.

Из таблицы видно, что в теннис может играть только Алексей.

Из условий 1 и 2 следует, что Борис не футболист. Таким образом, в футбол играет Алексей. Продолжим заполнять таблицу. Внесем в пустые ячейки строки «Алексей» нули.

Окончательно получаем, что Борис увлекается хоккеем и бадминтоном. Итоговая таблица будет выглядеть следующим образом:

Ответ: Петр увлекается лыжами и плаванием, Борис играет в хоккей и бадминтон, а Алексей занимается футболом и теннисом.

Всего: 191    1–20 | 21–40 | 41–60 | 61–80 …

Добавить в вариант

Всего: 191    1–20 | 21–40 | 41–60 | 61–80 …

Задача 1

#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
bool f(int A, int B, int C, int D, int E, int F){
    return (!(!A || F) && B && !C && (!D || E));
}
int main() {
    int count = 0;
    for (int A = 0; A <= 1; ++A)
        for (int B = 0; B <= 1; ++B)
            for (int C = 0; C <= 1; ++C)
                for (int D = 0; D <= 1; ++D)
                    for (int E = 0; E <= 1; ++E)
                        for (int F = 0; F <= 1; ++F)
                            if (f(A, B, C, D, E, F) == false)
                                count++;
    cout << count;
    return 0;
}

Задача 2

Задача 3

Задача 4

bool f(int x, int y, int z, int w){
    return (((x && z) || !x) && !w && y);
}
int main() {
    cout << "x y z w F" << endl;
    for (int x = 0; x <= 1; ++x)
        for (int y = 0; y <= 1; ++y)
            for (int z = 0; z <= 1; ++z)
                for (int w = 0; w <= 1; ++w)
                    if (f(x, y, z, w) == true)
                        cout << x << " " << y << " "
                            << z << " " << w << " " << f(x, y, z, w) << endl;
    return 0;
}

Задача 5

bool f(int x, int y, int z, int w){
    return ((!y || w) || (!x && z));
}
int main() {
    cout << "x y z w F" << endl;
    for (int x = 0; x <= 1; ++x)
        for (int y = 0; y <= 1; ++y)
            for (int z = 0; z <= 1; ++z)
                for (int w = 0; w <= 1; ++w)
                    if (f(x, y, z, w) == false)
                        cout << x << " " << y << " "
                            << z << " " << w << " " << f(x, y, z, w) << endl;
    return 0;
}

Задача 6

Задача 7

#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
bool f(int x, int y, int z){
    return ((x || y) && (!z || y));
}
int main() {
    cout << "x y z F" << endl;
    for (int x = 0; x <= 1; ++x)
        for (int y = 0; y <= 1; ++y)
            for (int z = 0; z <= 1; ++z)
                    if (f(x, y, z) == false)
                        cout << x << " " << y << " "
                            << z << " " << f(x, y, z) << endl;
    return 0;
}

Задача 8

Задача 9

Задача 10

Задача 11

Задача 12