Логика высказываний

Логика

Логика в информатике как учебной дисциплине была введена в самых первых учебниках информатики Каймина в 1985 году и в учебник информатики Каймина для средних школ в 1987-89гг. Парадокс в том, что первых школьных учебниках информатики Ершова, Кушниренко и многих действующих учебниках информатики для школ и вузов логика отсутствует.

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

Наибольшее значение логика приобретает в анализе алгоритмов и программ при решении задач на ЭВМ, когда от результатов решения задач зависят оценки на экзаменах или победа на олимпиадах по информатике или программированию.

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

Логика очень древняя наука.

1-й этап связан с работами ученого и философа Аристотеля (384-322 г.г. до н.э.). Он пытался найти ответ на вопрос “Как мы рассуждаем”, изучал правила мышления. Аристотель впервые дал систематическое изложение логики. Он подверг анализу человеческое мышление, его формы – понятие, суждение, умозаключение. Так возникла формальная логика.

2-й этап – появление математической, или символической, логики. Основы ее заложил немецкий ученый и философ Г.В. Лейбниц (1646-1716). Он сделал попытку построить первые логические исчисления, считал, что можно заменит простые рассуждения действиями со знаками, и привел соответствующие правила. Но он выдвинул только идею, а развил её окончательно англичанин Д. Буль (1815-1864). Буль считается основоположником математической логики как самостоятельной дисциплины. В его работах логика обрела свой алфавит, свою орфографию и грамматику.

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

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

Опр.2 Понятие – это форма мышления, выделяющая существенные признаки предмета или класса предметов, позволяющих отличить их от других.

Например: компьютер, трапеция, портфель, ураганный ветер.

Понятие имеет две стороны: содержание и объем.

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

Объем понятия – множество предметов, каждому из которых принадлежат признаки, составляющие содержание понятий.

Например:

1. Объем понятия город – это множество, состоящее из городов, носящих имя Москва, Одесса, Казань, Уфа, Нижнекамск и др. 
2. Объем понятия персональный компьютер – совокупность существующих в мире персональных компьютеров.

Опр.3 Суждение (высказывание, утверждение) – это форма мышления, в которой что-либо утверждается или отрицается о свойствах реальных предметов и отношениях между ними.

Высказывание может быть либо истинным, либо ложным, и может быть либо простым, либо составным (сложным).

Например:

1. Истинное и простое высказывание: Буква “т” - согласная.
2. Ложное и сложное высказывание: Осень наступила, и грачи прилетели.

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

Например:

1. Уходя, гасите свет!
2. Кто хочет быть счастливым?

Высказывания могут выражаться с помощью математических, физических, химических и прочих знаков. Например: 53, H₂O+SO₂=H₂SO₄.

.

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

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

Например:

Опр.5 Алгебра логики (алгебра высказываний) – раздел математической логики, изучающий строение (форму, структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.

Под высказыванием (суждением) будем понимать повествовательное предложение, относительно которого можно сказать, истинно или ложно.

В алгебре высказываний простым высказываниям ставятся в соответствии логические переменные,

обозначаемые прописными буквами латинского алфавита.

Например:

А= “Листва на деревьях опадает осенью”.
В= “Земля прямоугольная”.

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

Например:

А=1
В=0

Опр.6 В алгебре высказываний высказывания обозначаются именами логических переменных, которые могут принимать лишь два значения: “истина” (1) и “ложь” (0).

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

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

Рассмотрим три базовых логических операций – инверсию, конъюнкцию, дизъюнкцию и дополнительные – импликацию и эквиваленцию.

Алгоритм построения таблицы истинности.

     1. Определить количество наборов входных переменных - всевозможных сочетаний значений переменных, входящих в выражения, по формуле: Q=2ⁿ , где n - количество входных переменных. Оно определяет количество строк таблицы.
     2. Внести в таблицу все наборы входных переменных.
     3. Определить количество логических операций и последовательность их выполнения.
     4. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности.

Чтобы не повторить или не пропустить ни одного возможного сочетания значений входных переменных, следует пользоваться одним из предлагаемых ниже способов заполнения таблицы.
     Способ 1. Каждый набор значений исходных переменных есть код числа в двоичной системе счисления, причем количество разрядов числа равно количеству входных переменных. Первый набор - число 0. Прибавляя к текущему числу каждый раз по 1, получаем очередной набор. Последний набор - максимальное значение двоичного числа для данной длины кода.
     Например, для функции от трех переменных последовательность наборов состоит из чисел:

Способ 2. Для функции от трех переменных последовательность данных можно получить следующим путем:
     а) разделить колонку значений первой переменной пополам и заполнить верхнюю половину нулями, нижнюю половину единицами;
     б) в следующей колонке для второй переменной половинку снова разделить пополам и заполнить группами нулей и единиц; аналогично заполнить вторую половинку;
     в) так делать до тех пор, пока группы нулей и единиц не будут состоять из одного символа.
     Способ 3. Воспользоваться известной таблицей истинности для двух аргументов. Добавляя третий аргумент, сначала записать первые 4 строки таблицы, сочетая их со значением третьего аргумента, равным 0, а затем еще раз записать эти же 4 строки, но теперь уже со значением третьего аргумента, равным 1. В результате в таблице для трех аргументов окажется 8 строк:

Например, построим таблицу истинности для логической функции:

Количество входных переменных в заданном выражении равно трем (A,B,C). Значит, количество входных наборов Q=2³=8.
     Столбцы таблицы истинности соответствуют значениям исходных выражений A,B,C, промежуточных результатов  и (B V C), а также искомого окончательного значения сложного арифметического выражения :

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

1. инверсия,

2. конъюнкция,

3. дизъюнкция,

4. импликация и эквивалентность.

Операции одного приоритета выполняются слева направо. Для изменения порядка действий используются скобки.

Например: дана формула 

Порядок вычисления:

 - инверсия
 - конъюнкция
 - дизъюнкция
 - импликация
 - эквивалентность.

Основные законы логики

Правило коммуникативности - при операциях логического умножения и сложения переменные можно менять местами 

Правило ассоциативности - если в выражении используются только операции логического умножения или логического сложения то можно пренебрегать скобками или произвольно расставлять переменные 

Правило дистрибутивности - в алгебре высказываний можно выносить за скобки как общие множители так и общие слагаемые

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

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

Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул:

1)    

2)    
(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией);

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

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

5)    
(сначала добиваемся, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого дважды применяем правило де Моргана; затем используем закон двойного отрицания);

6)    
(выносятся за скобки общие множители; применяется правило операций с константами).

Задачи

Задание 1. 

Сколько различных решений имеет уравнение
(K v L v M) ^ (¬L ^ ¬M ^ N) = 1,
где K, L, M, N – логические переменные?

Решение.

Высказывание (K v L v M) ^ (¬L ^ ¬M ^ N) истинно только в том случае, когда истинны оба высказывания (K v L v M) и (¬L ^ ¬M ^ N).

Второе из этих высказываний, (¬L ^ ¬M ^ N), истинно только при L = 0, M = 0, N = 1.

При найденных значениях L и M первое высказывание, (K v L v M), истинно, если K = 1.

Уравнение имеет только одно решение.

Задание 2. Сколько различных решений имеет уравнение
(K ^ L) v (M ^ N) = 1,
где K, L, M, N – логические переменные?

Решение.

Высказывание (K ^ L) v (M ^ N) истинно, когда истинно хотя бы одно из высказываний (K ^ L), (M ^ N).

Первое из этих высказываний, (K ^ L), истинно при K = 1, L = 1, а поскольку второе высказывание при этом может принимать любое значение, то для M и N следует учитывать четыре различных набора: (0, 0), (0, 1), (1, 0), (1, 1).

Второе из этих высказываний, (M ^ N), истинно при M = 1, N = 1, а поскольку первое высказывание при этом может принимать любое значение, то для K и L следует учитывать четыре различных набора: (0, 0), (0, 1), (1, 0), (1, 1). Последний из этих наборов следует исключить, т.к. он уже учитывался ранее, когда M и N могли принимать любые значения.

Таким образом, уравнение имеет 7 решений.

Задание 3. Найти отрицание следующего высказывания: "Если урок будет интересным, то никто из учеников (Миша, Вика, Света) не будет смотреть в окно".
    

Решение.
     Обозначим высказывания:
     Y - "Урок интересный";
     M - "Миша смотрит в окно";
     B - "Вика смотрит в окно";
     C - "Света смотрит в окно".

     
     При упрощении выражения использовались формула замены операций и закон де Моргана.

.
     

Задание 4.  Определить участника преступления, исходя из двух посылок:
     1) "Если Иванов не участвовал или Петров участвовал, то Сидоров участвовал";
     2) "Если Иванов не участвовал, то Сидоров не участвовал".
     Решение. Составим выражения:  
     I - "Иванов участвовал в преступлении";
     P - "Петров участвовал в преступлении";
     S - "Сидоров участвовал в преступлении".
     Запишем посылки в виде формул:
     
     Тогда
     

Проверим результат, используя таблицу истинности:

Ответ: Иванов участвовал в преступлении.

Задание 5.

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

Число делится на 6 тогда и только тогда, когда оно делится на 2 и

на 3.

Число не делится на 6, но делится на 3. Следовательно, число не

делится на 2.

Решение.

Для проверки правильности некоторых высказываний можно воспользо-

ваться методом от противного. Его суть в следующем:

Пусть высказывание

В имеет значение ложно, а каждая из посылок А1, А2, ...,Аn. Допустим

теперь, что В имеет значение ложно, а каждая из посылок Аi - значение

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

истинных значений для основных высказываний. Если анализ покажет, что

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

Введем следующие высказывания:

А - число делится на 6

В - число делится на 2

С - число делится на 3

Тогда приведенное рассуждение можно записать:

АB and C, not A and C -- not B.

Решим методом от противного.

Пусть not В ложно, а основные высказывания AB and C и not A and C истинны. Так как not B - ложно, то В - истинно. Так как not A and C истинно, то not A=1 и С=1 или А=0 и С=1. Поскольку В и С истинны, то ВС=1, а так как А ложно то АВС ложно, но по предположению АВС истинно. Полученное противоречие доказывает правильность рассуждений, то есть число не делится на 2.

Задание 6. Представим такую ситуацию: по телевизору синоптик объявляет прогноз погоды на завтра и утверждает следующее:

1. Если не будет ветра, то будет пасмурная погода без дождя.

2. Если будет дождь, то будет пасмурно и без ветра.

3. Если будет пасмурная погода, то будет дождь и не будет ветра.

Так какая же погода будет завтра?

Решение:

а) Выделим простые высказывания и запишем их через переменные:

A – «Ветра нет»

B – «Пасмурно»

С – «Дождь»

б) Запишем логические функции (сложные высказывания) через введенные переменные:

1. Если не будет ветра, то будет пасмурная погода без дождя:

__

A → B & C

2. Если будет дождь, то будет пасмурно и без ветра:

С → B & A

3. Если будет пасмурная погода, то будет дождь и не будет ветра

B → C & A

в) Запишем произведение указанных функций:

_

F=(A→ B & C) & (C→B & A) & (B→ C & A)

г) Упростим формулу (используются законы де Моргана, переместительный закон, закон противоречия):

_

F=(A→ B & C) & (C→B & A) & (B→ C & A)
_ _ _ _

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

_ _ _ _

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

_ _ _ _ _ _

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

_ _ _ _ _ _ _

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

_ _ _

= A&B&C

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

_ _ _

F = A & B & C = 1

е) Проанализируем результат:

Логическое произведение равно 1, если каждый множитель равен 1.

Поэтому:

_ _ _

A = 1; B = 1; C = 1;

Значит: A = 0; B = 0; C = 0;

Ответ: погода будет ясная, без дождя, но ветреная.

Задание 7.

Три подразделения  А, В, С – торговой фирмы стремились получить по итогам года максимальную прибыль. Экономисты высказывали следующие предположения:
1.А получит максимальную прибыль только тогда, когда получат максимальную прибыль В и С. 
2.Либо А и С получат максимальную прибыль одновременно, либо одновременно не получат.
3.Для того, чтобы С получило максимальную прибыль, необходимо, чтобы и В получило максимальную прибыль.
По завершении года оказалось, что одно из трёх предположений ложно. Какие из названных подразделений получили максимальную прибыль?

Решение
Рассмотрим простые высказывания:
А={А получит максимальную прибыль},
В={В получит максимальную прибыль},
С={С получит максимальную прибыль}
Запишем на языке алгебры логики прогнозы, высказанные экономистами:
1) F1=  A = B & C;
2) F2=  A&C + A&C;
3) F3=  C =B.
Теперь составим таблицу истинности для F1, F2, F3.

  
Теперь вспомним, что ложным оказался один из прогнозов – F1, F2, F3. Эта ситуация соответствует четвертой строке таблицы.
Ответ: В и С получат максимальную прибыль .

1. Информатика и информационные технологии. Учебник для учащихся 10-11 классов. / Угринович Н.Д., - М. Лаборатория Базовых Знаний, 2004.

2. Практикум по информатике и информационным технологиям. Учебное пособие для общеобразовательных учреждений. / Угринович Н.Д., Босова Л.Л., Михайлова Н.И. - М. Лаборатория Базовых Знаний, 2001.

3. Логика в информатике. / Лыскова В.Ю., Ракитина Е.А. - М. Лаборатория Базовых Знаний, 2001.

4. http://www.urok-informatiki.ru

5. http://inf1.info

6. festival.1september.ru

7. www.metodichka.net

8. http://www.ido.rudn.ru/nfpk/inf

9. http://edu.h1.ru