Методика преподавания темы Основы логики

99

Основы логики.

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

Логика - наука о способах и формах мышления, которая возник­ла в Древнем Китае и Индии. Основоположником формальной логики по праву считается Аристотель.

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

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

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

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

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

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

F = А & В.

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

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

F = A v B

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

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

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

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

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

Л

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

Таблицы истинности можно построить для каждого логического выражения. Она определяет его значение при всех возможных комбинациях значе­ний логических переменных.

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

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

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

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

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

Например:

Составим таблицу истинности для логического выражения

1

. Количество переменных n=2, следовательно количество строк N = 4

2. Количество переменных мы определили, оно равно 2, теперь определим количество операций:

З

начит таблицы истинности будет иметь семь столбцов.

3. Построим исходную таблицу:

A

0

0

0

1

1

0

1

1

4. Воспользовавшись таблицами истинности логических элементов, заполним полученную таблицу по столбцам:

A

0

0

0

1

1

1

0

0

1

1

1

0

1

1

1

0

1

0

1

1

1

1

1

1

0

0

0

0

Таким образом можно определить значение любой логической функции..

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

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

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

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

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

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

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

А=А

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

А & А =0.

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

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

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

Закон коммутативности. Как и в алгебре: от перемены мест …

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

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

(A&B)v(A&C)=A&(B v С)

(A v В) & (A v С) = A v (B & C)

Пример. Упростить логическое выражение:

(A&B)v(A&В)

По закону дистрибутивности вынесем за скобки В:

(A&B)v(A&В)= B & (A v A)

Так как

(A v A)=1

тогда получим:

(A&B)v(A&В)=В & 1 = В.

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

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

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

НЕ

X Z

Х

НЕ Х

1

0

0

1

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

X

ИЛИ

Х

Y

Z

0

0

0

0

1

1

1

0

1

1

1

1

Y Z

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

X Z

И

Х

Y

Z

0

0

0

0

1

0

1

0

0

1

1

1

Y

Из тысяч и миллионов таких элементов строится ЭВМ.

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

0+0=00

0+1=01

1+0=01

1+1=10

Составим таблицу истинности для этого сумматора, обозначив слагаемые Х и Y, а результаты Р и Z:

Х

Y

Р

Z

0

0

0

0

0

1

0

1

1

0

0

1

1

1

1

0

Результаты можно записать в виде логических функций:

Р = Х и Y

Z = (Х или Y) и не ( Х и Y)

Логическая схема двухразрядного сумматора имеет вид:

Х

ИР = Х и Y

НЕ

Y

И

Z = (Х или Y) и не ( Х и Y)

ИЛИ

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

5. Тренировочные тестовые задания по теме «Основы логики»

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

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

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

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

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

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

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

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

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

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

1. Для какого числа X истинно высказывание

X>1 /\ ((X<5) -> (X<3))

1)

1

2)

2

3)

3

4)

4

2. Для какого из указанных значений числа X истинно высказывание:

(X>4) \/ ((X>1) ->(X>4))?

1)

1

2)

2

3)

3

4)

4

3. Для какого числа X истинно высказывание

((X>3) \/(X<3)) -> (X<1)

1)

1

2)

2

3)

3

4)

4

4. Какое логическое выражение равносильно выражению ¬ (A /\ B) /\ ¬C?

1)

¬A \/ B \/ ¬C

2)

(¬A \/ ¬B) /\ ¬C

3)

(¬A \/ ¬B) /\ C

4)

¬A /\ ¬B /\ ¬C

5. Для какого имени истинно высказывание:

¬ (Первая буква имени гласная -> Четвертая буква имени согласная)?

1)

ЕЛЕНА

2)

ВАДИМ

3)

АНТОН

4)

ФЕДОР

6. Какое логическое выражение равносильно выражению ¬ (А \/ ¬B) ?

1)

A \/ B

2)

A /\ B

3)

¬A \/ ¬B

4)

¬A /\ B

7. Укажите, какое логическое выражение равносильно выражению
¬ (¬А /\ B)

1)

A \/ ¬B

2)

¬A \/ B

3)

B /\ ¬A

4)

A /\ ¬B

8. Какое логическое выражение равносильно выражению

¬ (¬A \/ B) \/ ¬C?

1)

(A /\ ¬B) \/ ¬C

2)

¬A \/ B \/ ¬C

3)

A \/ ¬B \/ ¬C

4)

(¬A /\ B) \/ ¬C

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

Дан фрагмент таблицы истинности выражения F:

X

Y

Z

F

0

0

0

0

1

1

0

1

1

0

0

1

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

1)

¬X \/ ¬Y \/ ¬Z

2)

X /\ ¬Y /\ ¬Z

3)

X \/ Y \/ Z

4)

X /\ Y /\ Z

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

Дан фрагмент таблицы истинности выражения F:

X

Y

Z

F

0

1

0

0

1

1

0

1

1

0

1

0

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

1)

¬X \/ Y \/ ¬Z

2)

X /\ Y /\ ¬Z

3)

¬X /\ ¬Y /\ Z

4)

X \/ ¬Y \/ Z

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

Дан фрагмент таблицы истинности выражения F:

X

Y

Z

F

0

0

0

1

0

0

1

0

0

1

0

0

Чему равно F?

1)

X/\Y/\Z

2)

¬X\/¬Y\/Z

3)

X/\Y/\¬Z

4)

¬X/\¬Y/\¬Z

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

Дан фрагмент таблицы истинности выражения F:

X

Y

Z

F

0

0

0

1

0

0

1

0

0

1

0

1

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

1)

¬X/\¬Y/\Z

2)

¬X\/¬Y\/Z

3)

X\/Y\/¬Z

4)

X\/Y\/Z

13. Для составления цепочек используются бусины, помеченные буквами: A, B, C, D, E. На первом месте в цепочке стоит одна из бусин A, C, E. На втором - любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На третьем месте - одна из бусин C, D, E, не стоящая в цепочке на первом месте.

Какая из перечисленных цепочек создана по этому правилу?

1)

CBE

2)

ADD

3)

ECE

4)

EAD

14. Для составления цепочек разрешается использовать бусины 5 типов, обозначаемых буквами А, Б, В, Е, И. Каждая цепочка должна состоять из трех бусин, при этом должны соблюдаться следующие правила:

1)

на первом месте стоит одна из букв: А, Е, И,

2)

после гласной буквы в цепочке не может снова идти гласная, а после согласной - согласная,

3)

последней буквой не может быть А.

Какая из цепочек построена по этим правилам?

1)

АИБ

2)

ЕВА

3)

БИВ

4)

ИБИ

15. Цепочка из трех бусин формируется по следующему правилу:
На первом месте в цепочке стоит одна из бусин А, Б, В. На втором - одна из бусин Б, В, Г. На третьем месте - одна из бусин А, В, Г, не стоящая в цепочке на первом или втором месте.

Какая из следующих цепочек создана по этому правилу:

1)

ББГ

2)

ВАГ

3)

БГГ

4)

АГБ

16. Для составления цепочек используются бусины, помеченные буквами: M, N, O, P, S. В середине цепочки стоит одна из бусин M, O, S. На третьем - любая гласная, если первая буква согласная, и любая согласная, если первая гласная. На первом месте - одна из бусин O, P, S, не стоящая в цепочке в середине.

Какая из перечисленных цепочек создана по этому правилу?

1)

SMP

2)

OSN

3)

SNO

4)

MSO

17. В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.

A

C

D

A

4

5

4

3

6

C

3

D

5

6

1)

2)

3)

4)

18. В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.

A

C

D

Е

A

1

4

1

1

3

C

4

2

D

3

Е

1

2

1)

2)

3)

4)

19. Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними.

Укажите таблицу, для которой выполняется условие: "Минимальная стоимость проезда из А в B не больше 6".

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

1)

2)

3)

4)

A

C

D

Е

A

3

1

4

2

C

3

4

2

D

1

Е

2

2

C

D

Е

A

3

1

1

4

C

3

4

2

D

1

Е

1

2

C

D

Е

A

3

1

4

1

C

3

4

2

D

1

Е

1

2

C

D

Е

A

1

4

1

C

4

4

2

D

1

4

Е

1

2

20. Укажите значения переменных K, L, M, N, при которых логическое выражение (¬K \/ M)->(¬L \/ M \/ N) ложно. Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1

1)

0101

2)

0100

3)

1011

4)

1100

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

(K/\L/\M)\/(¬L/\¬M/\N) = 1

где K, L, M, N - логические переменные?

В качестве ответа вам нужно указать только количество таких наборов.

1)

1

2)

2

3)

3

4)

4

22. Кто из четырех мальчиков разбил вазу, если Саша, Ваня, Коля и Олег делают вид, что происшедшее к ним не относится.

Коля не бил по мячу, сказал Саша. Это сделал Ваня.

Ваня ответил: Разбил Коля, Саша не играл в футбол дома.
Коля сказал: Я знаю, что Ваня не мог этого сделать. А я сегодня еще не сделал уроки. Олег сказал - А меня не было в комнате. Я был в библиотеке.
Оказалось, что один из мальчиков оба раза солгал, а трое в каждом из своих заявлений говорили правду.

Так кто же разбил вазу?

1)

Коля

2)

Ваня

3)

Саша

4)

Олег

23. Четыре школьника, Миша (М), Коля (К), Сергей (С) и Петр, остававшиеся в классе на перемене, были вызваны к директору по поводу разбитого в это время окна в кабинете. На вопрос директора о том, кто это сделал, мальчики ответили следующее:

Миша: «Я не бил окно, и Коля тоже…»

Коля: «Миша не разбивал окно, это Сергей разбил футбольным мячом!»

Сергей: «Я не делал этого, стекло разбил Миша».

Петр: «Я не делал этого, я выхрдил в этот момент в коридор».

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

Кто разбил стекло в классе?

1)

Коля

2)

Сергей

3)

Петр

4)

Миша

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

Один считает, что первой будет Наташа, а Маша будет второй.

Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место.

Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй.

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

Какое место на чемпионате заняли Наташа, Маша, Люда, Рита?

(В ответе выберите числа, соответствующие местам девочек в указанном порядке имен.)

1)

1234

2)

1342

3)

1423

4)

1243

Ответы к тесту по теме: «Основы логики»