Понятная информатика

 

 

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

Для более наглядного отображения логических отношений между множествами точек  А и В  будем использовать геометрическую схему в виде кругов Эйлера (рис.1).

 

Точка принадлежит множеству А, если она находится внутри круга, его ограничивающего, что

записывается в виде  А=1 (истина), иначе А=0 (ложь).

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

 

Результатом применения логических операций могут быть только истина (1) или ложь (0).

 

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

НЕ, И  и  ИЛИ:

 

• НЕ: инверсия (отрицание). Обозначается знаком ¬, например, ¬А). Результат применения:   ¬1 = 0,  ¬0 = 1,     т.е. истина превращается в ложь, а ложь – в истину.  Будем говорить,  что  операция  НЕ (¬)  переворачивает результат (значение);

 

• И:   конъюнкция (логическое умножение). Обозначается  знаками  ˄ либо &, 

                (например, А ˄ В либо А & В).  Результатом выполнения конъюнкции служит

                пересечение множеств  А и  В (на рис.2  выделено желтым  цветом). При этом точка

                принадлежит пересечению множеств А и В, если она принадлежит одновременно обоим

                множествам:

                                                         А & B = 1 при А=1 и В=1.

                Во всех остальных случаях в результате применения выражения  И  получаем ложь.

                Т.о,. исключение  № 1:

                                                            «И»  правда, когда все части выражения правда;

                          

• ИЛИ: дизъюнкция (логическое сложение). Обозначается ˅ (например, А ˅ В).

                   Результатом выполнения дизъюнкции служит объединение множеств  А и  В

                   (на рис.3  выделено  зеленым  цветом). При этом точка не принадлежит объединению

                   множеств А и В,  если  она  не принадлежит ни А, ни В:

                                                                  А  ˅  B = 0   при   А=0  и   В=0.  

                   Во всех остальных случаях в результате применения выражения  ИЛИ получаем  правду.

                   Т.о., исключение  № 2:

                                                             «ИЛИ»  ложно, когда все части выражения ложны.

 

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

 

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

 

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

 

Желающим решать задачи, открывая скобки в выражениях, необходимо знать законы алгебры логики!

 

Законы рефлексивности:   

               a ∧ a = a, то есть  0*0 =0 или 1*1 = 1

               a ∨ a = a, то есть  0+0=0  или 1+1 = 1

 

Законы коммутативности:

               a ∧ b = b ∧ a, то есть  a*b = b*a

               a ∨ b = b ∨ a, то есть  b+b = b+a

 

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

               (a ∧ b) ∧ c = a ∧ (b ∧ c), то есть (a*b) * c = 1 при a=b=c=1 или равно 0 в противном случае

               (a ∨ b) ∨ c = a ∨ (b ∨ c), то есть (a+b)+c = 0 при a=b=c=0  или равно 1 в противном случае

 

Законы дистрибутивности:  

               a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c), то есть  a*(b+c) = (a*b) + (a*c), то есть 0*(bVc) = 0 или 1*(bVc) = bVc

               a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) , то есть a+(b*c) = (a+b) * (a+c), то есть (1+b)*(1+c) = 1 или 0+(b*c) = b*c

 

Закон отрицания отрицания:   

                ¬ (¬ a) = a, то есть  -(-a) = a

 

Законы поглощения:

                a ∧ (a ∨ b) = a, то есть a*(a+b) равно 0 при а=0 или 1 – в обратном случае.

                a ∨ (a ∧ b) = a, то есть a+(a*b) равно 1 при а=1 или 0 – в обратном случае.

 

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

                ¬ (a ∧ b) = ¬ a ∨ ¬ b, то есть 0 при a=b=1 и =1 – в обратном случае.

                ¬ (a ∨ b) = ¬ a ∧ ¬ b, то есть  -(1) = 0 или –(0) = 1, то есть  =  0 при а=1 или b=1 и 1 – в обратном случае.

 

Другими словами:

 

Если перед скобкой стоит знак НЕ, то при открытии скобок следует менять на противоположные все знаки, стоящие перед выражениями ("+" на "-" и наоборот) и логические операции ("И" на "ИЛИ" и наоборот):

 

                 ¬ (А & В) = (¬ А) V (¬ В), то есть НЕ (А И В) = (НЕ А) ИЛИ (НЕ В)

                 ¬( А V  В) = (¬ А) & (¬ В), то есть НЕ (А ИЛИ В) = (НЕ А) И (НЕ В)

 

Например,

 

       НЕ ((Первая буква гласная) И (Последняя буква согласная)) = 

                                          =НЕ (Первая буква гласная) ИЛИ НЕ (Последняя буква согласная)

 

        При открытии скобок с математическими сравнениями внутри следует помнить, что знаков сравнения всего три: > (больше),  < (меньше) и = (равно), и при открытии скобок с отрицанием перед ними следует менять эти знаки на противоположные, то есть:

            НЕ ( > ) заменяется на (<=)

            НЕ ( < ) заменяется на (>=)

            НЕ (=) заменяется на два знака (<>)

 

или наоборот: 
            НЕ ( ≥  или  >= ) заменяется на ( < )

            НЕ ( ≤  или  <= ) заменяется на ( > )

            НЕ (<>) заменяется на ( = ).

 

Главное здесь – не забывать про строгое равенство – знак «=»!

 

 

Рассмотрим решение задач на примерах.

 

Задача 1

Для ка­ко­го из приведённых зна­че­ний числа X ложно высказывание: 

                                                  НЕ (X < 5) ИЛИ (X < 4) ?

1) 6  

2) 5

3) 4

4) 3

 

Решение:

Последней операцией при вычислении этого выражения будет ИЛИ, а для нее действует исключение № 2.

Следовательно,

                                       НЕ (X < 5)    ИЛИ     (X < 4)  =  0                                                                           

                             при            0           ИЛИ         0      =  0

                                                    

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

                                                  НЕ (X < 5) = 0 

                              при              НЕ (   1   )  =  0

          Отсюда следует, что  выражение в левой скобке соответствует истине, а в правой – лжи (соответственно, при открытии скобок переворачиваем математический знак на противоположный, не забывая и про знак «=»), т.е.                        

                                                             4 ≤ Х < 5

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

Ответ: 3

 

Задача 2

Для ка­ко­го из приведённых зна­че­ний числа X ис­тин­но высказывание:

                                                         НЕ (X < 7)  И  (X < 8)?

1) 5

2) 6

3) 7

4) 8

 

Решение:

Последней операцией при вычислении этого выражения будет И, а для нее действует исключение № 1.

Следовательно,

                                       НЕ (X < 7)      И      (X < 8) =  1                                                        

                               при            1          И          1      =  1

                                                   

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

Тогда                                        НЕ (X < 7)   =   1 

                              при              НЕ (   0   )   =   1

          Отсюда следует, что  выражение в левой скобке соответствует лжи (соответственно, при открытии скобок переворачиваем математический знак на противоположный, не забывая и про знак «=»), а в правой – истине т.е.                        

                                                     7  ≤ Х <  8

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

Ответ: 3

 

Задача 3

Для ка­ко­го из приведённых имён ложно высказывание:

                                   НЕ ((Первая буква гласная) И (Последняя буква согласная))?

 

1) Вера

2) Степан

3) Анна

4) Иван

 

Решение:

Запишем задание в виде схемы:

               НЕ (  (Первая буква гласная) И (Последняя буква согласная)  ) = 0          

     при    НЕ  (                                         И = 1                                            ) = 0

 

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

Поэтому применим для  решения выражения во внутренних скобках исключение № 1:

                               (Первая буква гласная)  И  (Последняя буква согласная) = 1

когда обе части выражения истинны, т.е. первая буква имени – гласная, а последняя согласная, что соответствует имени  Иван.

Ответ: 4

 

Задача 4

Для ка­ко­го из приведённых чисел ложно высказывание:

                                        (число < 40) ИЛИ НЕ (число чётное)  ?

1) 137 

2) 64                   

3) 9                 

4) 8

 

Решение:

Последней в этом выражении выполняется операция ИЛИ, тогда применяем исключение № 2.

Тогда                                     (число < 40)   ИЛИ   НЕ (число чётное)  =  0

                                                        0          ИЛИ   НЕ (         1            )  =  0

При открытии скобок в левой части выражения меняем знак  <  на   ≥, а в правой части учитываем, что отрицание перед скобкой переворачивает результат при ее открытии, т.е. в правой скобке записана истина.

Таким образом, получаем   (число ≥ 40)  ИЛИ (число четное), что соответствует числу 64.

Ответ:  2

 

 

Задача 5

Напишите наименьшее число x, для которого истинно высказывание:

                         (x > 16) И НЕ (x нечётное).

Решение:

Если  (x > 16) И НЕ (x нечётное) = 1, то   (х>16)=1, то есть  х ≥ 17,   

и  НЕ(х нечетное)=1, то есть  х - четное. Тогда наименьшим четным числом будет 18.

Ответ: 18

 

Задача 6

В таблице приведены запросы и количество страниц, которые нашел 

поисковый сервер по этим запросам в некотором сегменте Интернета:

Сколько страниц в тысячах будет найдено по запросу Корвет ?

 

Решение:

Применив формулу ИЛИ = А + В - И, получаем:

3320 = 2100 + Корвет - 1300

Тогда Корвет = 3320 - 2100 + 1300 = 2520

Ответ: 2520

Задача 7

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

Сколько страниц в тысячах будет найдено по запросу Швеция | Финляндия ?

 

Решение:

Применив формулу ИЛИ = А + В - И, получаем:

Швеция | Финляндия = 3200 + 2300 - 100 = 5400

 

Ответ: 5400