Информатика. Теория и  практика

Логика

 

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

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

 

Мышление осуществляется через

• понятия ,

• высказывания  (суждения,  утверждения),

• умозаключения .

 

      Понятие  – форма мышления,  фиксирующая основные  существенные признаки объекта. Имеет две стороны: содержание  и объем 

Содержание понятия составляет совокупность существенных признаков объекта.

       (Для раскрытия содержания понятия необходимо и достаточно перечислить все качества объекта, по которым его можно однозначно идентифицировать)

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

Пример: понятие компьютер:

1. Содержание

Устройство для автоматизированной обработки информации

Построено на основе микропроцессора

Имеет устройства ввода/вывода

2. Объем понятия компьютер – миллиарды единиц компьютерной техники по всему миру

 

         Высказывание – это Форма мышления, выражающая  формулировку своего понимания  мира, в котором либо что-то  утверждается, либо отрицается.

Строится на основе понятий и  выражается только повествовательным предложением.

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

Если связь понятий, на которых  построено высказывание, правильно  отражают свойства и отношения  реальных вещей, то такое  высказывание истинно

 

Высказывание, противоречащее  реальной действительности – ложное

  Пример:

Высказывание: «Буква «А» – гласная»   истинно

     Высказывание: «Компьютер был изобретен в середине XIX века»   ложно

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

 

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

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

Пример:

Даны высказывания:«Имеется равнобедренный треугольник»

«Все углы треугольника равны»

Получить высказывание «Этот треугольник - равносторонний» путем умозаключений.

 

Алгебра высказываний

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

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

Обозначаются буквами латинского алфавита: A, B, C…

 

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

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

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

Обозначаются F(A,B,C…). Также могут принимать значения «ИСТИНА» или «ЛОЖЬ» в зависимости от того, какие значения имеют входящие в их состав логические переменные и от действий над ними.

 

Логические операции

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

Обозначается F(A,B) = A & B  или   F(A,B) = A * B

Таблица истинности показывает какие значения принимает логическая функция при всех возможных значениях логических переменных

​

​

 

 

 

 

 

 

 

 

​

​

Конъюнкция, истинна тогда и только тогда, когда истинны все входящие в него логические переменные

 

2. Дизъюнкция (логическое сложение, «ИЛИ»)

Объединение двух или нескольких высказываний в одно с помощью союза «ИЛИ»

называется операцией логического сложения, или дизъюнкцией.

Обозначается F(A,B) = A Ú B или F(A,B) = A + B

​

Логическая функция, полученная в результате дизъюнкции, истинна тогда,

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

 

 

 

 

3. Инверсия (логическое отрицание, «НЕ»)

Обозначается: F(A) = ¬A  или   F(A) = Ā

​

​

​

​

​

​

​

​

4. Импликация (логическое следование, «Если А, то В»)

5. Эквивалентность (логическое равенство, «А тогда и только тогда, когда В»)

 

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

Импликация:

         А → В = ¬A v В или

         А  → В = ¬A v В или

         А → В = ¬A v В          

Эквивалентность:

         А ↔ В = (¬A v В) ^ (¬B v A) или

         А ↔ В = (¬A v В) ^ (¬B v A) или

         А ≡ В = (¬A v В) ^ (¬B v A)

​

​

6. Строгая дизъюнкция (сложение по модулю 2)

​

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

​

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

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

​

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

1. Выяснить количество строк (2^n, где n – количество переменных)

2. Выяснить количество столбцов (количество переменных + количество логических операций)

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

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

​

Пример

Построим таблицу истинности для функции 
F = (А v В) * (A ->B)

1. Переменных: две (А и В), т.е. N = 2, количество строк: 2^n=2^2=4. С заголовком: 5

2. Количество столбцов: 2 переменные + 3 операций. Итого 5.

3. Порядок операций:

                              1          3         2    

                   F = (А v В)  *  (A  ->B) 

​