Что такое логика в информатике

Логика в информатике

Содержание

Область применения

Включаются следующие основные применения:

Этот список продолжает пополняться.

Эффективность логики в компьютерных науках

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

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

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

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

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

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

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

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

Источник

Логика

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

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

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

Понятие имеет две основные логические характеристики: содержание и объем.

Содержание понятия

Содержанием понятия называется совокупность существенных признаков, отраженных в этом понятии.

Объем понятия

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

Совместимые и несовместимые понятия

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

Отношения совместимых понятий:

Отношения несовместимых понятий:

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

Высказывание характеризуется своим содержанием и формой.

Умозаключение — форма мышления, посредством которой из одного или нескольких высказываний, называемых посылками, мы по определенным правилам вывода получаем заключение.

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

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

Инверсия (отрицание)

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

В выражениях обозначается ¬A или A.

Читается «НЕ» (например, «не А»).

Конъюнкция (логическое умножение)

Конъюнкция — это логическая операция, образующая сложное высказывание, истинное тогда и только тогда, когда истинны оба исходных высказывания.

В выражениях обозначается A ∧ B или A & B (знак может не указываться — AB).

Читается «И» (например, «А и Б»)

Дизъюнкция (логическое сложение)

Дизъюнкция — это логическая операция, образующая сложное высказывание, истинное тогда, когда истинно хотя бы одно из исходных высказываний.

В выражениях обозначается A ∨ B, иногда A + B.

Читается «ИЛИ» (например, «А или Б»)

Импликация (следование)

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

В выражениях обозначается A ⇒ B или A → B.

Читается «ЕСЛИ. ТО» (например, «если А, то Б»)

Эквивалентность (равнозначность)

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

В выражениях обозначается A ⇔ B или A ≡ B.

Читается «ТОГДА И ТОЛЬКО ТОГДА, КОГДА» (например, «А тогда и только тогда, когда Б»)

Для записи логических функций часто используют таблицы истинности.

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

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

Источник

Что такое логика в информатике

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

Этапы развития логики

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

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

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

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

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

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

В алгебре логики все высказывания рассматриваются только с точки зрения логического значения, от их житейского содержания отвлекаются. Будем обозначать элементарные суждения заглавными буквами латинского алфавита. Единственно существенной характеристикой алгебры логики является истинность или ложность каждого высказывания. Значение истинности суждения обозначим числом 1 и 0, если значение ложное.

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

Пример: “В любом прямоугольном треугольнике один угол равен 90 градусов”, “Всякий человек- млекопитающий”.

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

Примеры: “Если треугольник равносторонний, то все его углы равны между собой”, “Если король под шахом и ему некуда ходить, то мат”.

Пример: “На Земле есть вода, атмосфера и жизнь” (“На Марсе есть вода и атмосфера, значит на Марсе есть жизнь”.

Пример: “Ученик 10”а” Петров опоздал на урок” (“Все ученики 10”а” опоздали на урок”).

Пример: “Все рыбы плавают”(“Окунь плавает”).

Алгебра суждений

Существуют логические операции:

Отрицание

Отрицанием суждения A называется новое суждение, которое является истинным, если суждение A ложно (и ложно, если суждение A истинно). Эту операцию называют инверсией или логическим “не”.
Обозначения: , не A, not A.

Таблица истинности логического “не”:

Конъюнкция

Конъюнкцией двух высказываний A и B называется новое высказывание, которое считается истинным, если A и B истинные, и ложным, если одно из них ложно. Данная операция соответствует союзу ”и”. Обозначения: A^B, A и B, A and B, A&B, A*B.

Источник

Логика: предикатная, формальная и сентенциальная. Кванторы и возникновение информатики

1 | Введение

Логика, как эпистемологический инструмент, — исследующий знание как таковое, — изобретена независимо в трёх отдельных государствах: Греции (Аристотелем), Китае (до правления Цинь Шихуанди) и Индии. В последних двух государствах логика не распространилась настолько, чтобы получить полноценное развитие. В античной же Греции логика сформировалась в своих основах столь определённо, что дополнилась только через 2 тысячелетия.

Значительные изменения в греческую логику, помимо Буля, Моргана и Рассела, внёс Фреге — самая важная фигура основателей формальной семантики. Он разработал логику предикатов и 2 вида кванторов, попытавшись создать «логически совершенный язык» о котором мечтал Лейбниц. Значимой личностью является также Гёдель, который открыл знаменитые две теоремы о неполноте, описывающие невозможность объединения множества доказуемых утверждений со множеством истинных. Он утверждал, что доказательства математики зависят от начальных предположений, а не фундаментальной истины, из которой происходят ответы. Одна из главных идей его работ состоит в том, что ни один набор аксиом, — в том числе математических, — не способен доказать свою непротиворечивость.

На этом этапе некоторые заметят влияние платонизма на австрийского логика. Совершенно верно, ведь Гёдель не раз заявлял о влиянии метафизики Платона на собственную деятельность. Но сам Платон развитию формальной логики способствовал лишь косвенно: в истории он вносит вклад в развитие другого направления — философской логики. Платоном созданы вопросы, на которых основывается вся западная академическая философия вплоть до наших дней. Философия, в том виде, котором она известна, возникла только благодаря учителю Аристотеля.

Платон — учитель Аристотеля

В другие периоды в логику также вносили дополнения:

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

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

Но главное, что сами логические операции не изменились. «Органон» Аристотеля, как сборник из 6 книг — первоисточник, где подробно описаны главные логические законы. «Органон» (с древнегреческого ὄργανον), означает — инструмент. Аристотель считал, что логика является инструментом к познанию. Он объединяет методом получения информации такие науки:

Физика — наука о природе;

Метафизика — наука о природе природы;

Биология — раздел физики, наука о жизни;

Психология — раздел физики, наука о душе;

Кинематика — раздел физики, наука о движении;

2 | Терминология

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

Сам Аристотель находит логике как средству убеждения иное применение: в риторике, спорах, дебатах, выступлениях и т.д., описывая это в труде «Риторика». В западной философии принято давать чёткие определения перед рассуждениями, поэтому определимся с терминами. Логика — наука о правильном мышлении.

В языковой зависимости возникают трудности трактовки термина «наука», но даже в оригинальном названии труда Фридриха Гегеля «Наука логики» — «Wissenschaft der Logik», употребляется слово «наука» (Wissenschaft). Поэтому придём к консенсусу и будем считать, что научной можно назвать ту дисциплину, в которой возможны открытия, исследование и анализ. Логика в таком случае — наука, ибо внутри неё возможно совершать открытия. Яркий пример — комбинаторика Лейбница.

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

Слово «мышление» понимается на интуитивном уровне, но чёткое объяснение затруднительно, обширно и иногда не объективно.

Бюст Аристотеля

3 | Формальная и неформальная логика

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

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

Законы формальной логики:

1. Закон тождества (А = А): эквивокация или двусмысленность недопустимы. Нельзя подменять одно понятие, другим.

2. Закон непротиворечия (А ∧ ¬А = 0): одно и то же утверждение не может быть истинным и ложным одновременно.

3. Закон исключения третьего или бивалентности (А ∨ ¬А = 1): утверждение может быть либо истинным, либо ложным — третьего не дано.

Принципы формальной логики:

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

4 | Сентенциальная логика (алгебра высказываний)

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

Отрицание (Утверждение ¬A истинно тогда и только тогда, когда A ложно): если имеем утверждение «А» и имеем утверждение «не А», то, когда утверждение «А» будет истинным — утверждение «не А» будет ложным. Также и когда утверждение «А» будет ложным — утверждение «не А» будет истинным.

Конъюнкция (Утверждение A ∧ B истинно, если и A, и B — истинны. Ложно в противном случае): в английском языке — союз «and/&»; в русском — «и». В утверждении «А и В», между «А» с «В» стоит знак конъюнкции — «∧». Утверждение «А и В» является истинным, если «А» с «В» являются истинными одновременно. Если хоть один элемент ложен, то всё утверждение ложно. «А и В» подразумевает, во-первых: истинность «А», во-вторых: истинность «В».

Дизъюнкция (Утверждение A ∨ B верно, если A или B (или оба) верны. Если оба не верны — утверждение ложно): в английском языке — союз «or»; в русском — «или». Существует два типа дизъюнкции — включающая и исключающая (в логике используется включающее «или»). Условия таковы, что утверждение «А или В» будет истинным, когда один или оба элемента истинны, но никогда — когда оба элемента ложны. Это противоречит нашему обыденному мышлению, т.к. когда спрашивают: «Чай или кофе?» мы выбираем один элемент, но в логике подразумевается выбор не только одного, а нескольких возможных.

Импликация (Утверждение A ⇒ B ложно, только когда A истинно, а B ложно): в английском языке — «therefore»; в русском языке — «следовательно». Подразумевает истинность одного элемента при истинности другого. Потому что условия истинности соблюдаются всегда, кроме случая, когда «А» истинно, а «B» ложно. Поэтому утверждение: «А» ложно, следовательно «B» ложно — истинно. Покажется, что когда «А» ложно, а «В» истинно — не соблюдаются условия, но это не так. Если вы скажете, что после дождя промокните — это утверждение будет истинным вне зависимости от того, пошёл дождь или нет.

Эквивалентность (Утверждение A ⇔ B истинно, только если оба значения A и B ложны, либо оба истинны): если истинно утверждение «А, следовательно В» и истинно утверждение «В, следовательно А», то истинными являются выражения «А эквивалентно В» и соответственно «В эквивалентно А». Условия истинности соблюдаются в случаях, когда оба элемента истинны или оба ложны.

Значение переменных

5 | Предикатная логика первого порядка

В XX веке, после добавлений в область логики работ Лейбница и Фреге, на основе этой дисциплины создаётся новая — информатика. Программирование сохраняет преемственность с видоизменённой логикой Аристотеля — предикатной логикой, описательная способность которой выше, чем у логики высказываний (сентенциальной).

Прежде чем разобрать этот новый тип логики, поговорим об её отличии от сентенциальной. Главная особенность предикатной логики, что заглавными буквами обозначаются предикаты, а не целые высказывания. Можно сказать, что предикат — это математическая функция, которая «накладывает» множество субъектов на множество утверждений.

Высказывание «Я пошёл в зоопарк» — состоит из субъекта и предиката. В нём субъект — «Я», а предикат — то, что остаётся кроме субъекта («пошёл в зоопарк»). Субъект — тот, кто совершает действие в предложении или имеет выраженное свойство; предикат — всё оставшееся. Таким образом, если в сентенциальной логике высказывание «Я пошёл в зоопарк» выражалось бы одной заглавной буквой, то в логике предикатов использовались бы две буквы (заглавная и подстрочная): «P» — для предиката; «x» — для субъекта. Субъекты обозначаются переменной («x»), потому что в предикатной логике появляются две относительно новые операции: универсальный и экзистенциальный кванторы. Особенность кванторов заключается в том, что ими возможно записать выражение истинное при всех возможных переменных «х» или хотя бы при одном.

Универсальный квантор (квантор всеобщности) обозначается символом — «∀», с указанием переменной под ним. Возьмём утверждение «Все пингвины чёрно-белые». В логике высказываний оно бы выражалось как «X ⇒ P», где «X» — нечто являющееся пингвином, а «P» — нечто являющееся чёрно-белым. В предикатной логике же используются субъекты и предикаты, поэтому нечто являющееся пингвином (субъект), обозначалось бы переменной «х» снизу под предикатом. «»х» — является пингвином, следовательно, является чёрно-белым». Записывается так: P(х) ⇒ B(х), где P(х): х — пингвин; B(х): x — чёрно-белый.

Однако этого недостаточно, ведь непонятно, один субъект «х» чёрно-белый или больше одного, а может вообще все. Поэтому утверждение «»х» — является пингвином, следовательно, является чёрно-белым», берётся в скобки и перед скобками используется символ «∀» с переменной «х» под ним — которые вместе и будут универсальным квантором.

Универсальный квантор переводится как: «Для всех «х» истинно, что …». Теперь утверждение «х — является пингвином, следовательно, является чёрно-белым» с универсальным квантором перед ним, расшифровывается так: «Для всех «х» истинно, что «х» — является пингвином, следовательно, является чёрно-белым». Это означает, что чем бы ни был объект во вселенной, если этот объект пингвин — он является чёрно-белым. Полная запись будет выглядеть так:

Экзистенциальный квантор (квантор существования) обозначается символом — «∃» с указанием переменной под ним. Возьмём утверждение «Некоторые пингвины серые». Как и в прошлый раз, выражение «»x» — является пингвином и «х» — является серым» возносим в скобки и ставим перед ними квантор, в этом случае экзистенциальный с указанной переменной. «»x» — является пингвином и «х» — является серым» записывается так: P(х) ∧ C(х), где P(х): х — пингвин; C(х): x — серый.

Экзистенциальный квантор можно перевести так: «Есть такой «х», для которого будет истинно, что …». Подразумевается, что есть как минимум один «х», для которого выполняются условия выражения. Если вам говорят, что ДНК не существует, достаточно показать одну молекулу дезоксирибонуклеиновой кислоты для опровержения этого утверждения. Также и с кванторами, если существует хотя бы один серый пингвин, то утверждение об отсутствии серых пингвинов будет ложно. Полная запись экзистенциального квантора для выражения «Есть такой «х», для которого будет истинно, что «x» — является пингвином и «х» — является серым», будет выглядеть так:

6 | Заключение

Примечательно, что есть возможность перевода одного вида квантора в другой. Возьмём утверждение «Все пингвины не являются серыми». Для универсального квантора текстовая запись будет такая: «Для всех «х», будет истинным утверждение о том, что если «х» — является пингвином, то «х» — не является серым объектом». Но утверждение изменяется и для экзистенциального квантора, используя знак отрицания: «Нет такого «х», для которого бы было истинным утверждение о том, что «x»— является пингвином и «х»— является серым».

В середине XIX века, Готлоб Фреге дополнил логику Аристотеля двумя этими операциями, которые позже сформировались в отдельную дисциплину — предикатную логику. С введением в логику экзистенциального квантора (после универсального) — предикатная логика, в основе своей, завершилась как система…

Источники:

1 — Аристотель: «Органон» — «Первая аналитика» и «Вторая аналитика»;

2 — Аристотель: «Риторика»;

3 — Готлоб Фреге: «Исчисление понятий»;

4 — «Monatshefte für Mathematik und Physik» 1931 г.: Курт Гёдель «О принципиально неразрешимых положениях в системе Principia Mathematica и родственных ей системах»;

5 — The Early Mathematical Manuscripts of Leibniz;

6 — Мельников Сергей: «Введение в философию Аристотеля»;

7 — Гильмутдинова Нина: «Логика и теория аргументации»;

Источник

Что такое логика в информатике

Логика – это бог мыслящих…

Не мыслям надобно учить, а мыслить.

Два основных достояния человеческой природы
это ум и рассуждения.

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

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

Первое упоминание логики встречается в китайской «Книге перемен»(VIII в. до н.э.). В Древней Греции она начала разрабатываться в VI в. до н.э. Немного позже логика возникла в Индии. Первоначально логика служила юриспруденции и ораторскому искусству. Еще одним стимулом создания науки логики стали запросы математики, где требовались строгие доказательства.

Первые общие схемы правильных рассуждений систематически были изложены уже в древности греческим философом Аристотелем (384-322 г. до н. э.). Независимо от него несколько иными видами схем правильных умозаключений и другие философы. Затем в средние века были несколько развиты и пополнены древние схемы умозаключений. Позже, в новое время, некоторый прогресс в логике наступил благодаря философу и математику Г. В. Лейбницу (1646-1716). Великий русский и швейцарский ученый Леонард Эйлер(1707-1783) с 1727г. по 1741г. работал в России. С 1766г. был избран академиком Петербургской АН. Ученый необычайной широты интересов. Автор свыше 800 работ по математике, физике, небесной механике, оптике, баллистике, кораблестроению, теории музыки. Предложил так называемые круги Эйлера, ставшие основой формальной логики.

Основоположником математической логики считается Джордж Буль(1815-1864),английский математик, отец всемирно известной писательницы Этель Лилиан Войнич.

Со второй половины XIX и в ХХ вв. благодаря работам Дж. Буля, Г. Фреге (1848-1925) и других ученых в логике начался период интенсивного развития, приведшего к тому, что логика стала самостоятельной, содержательной научной дисциплиной. Этот последний период бурного развития логики имеет своим источником разработку вопросов обоснования математики. В самом деле, математика представляет собой такую науку, в которой умозаключение играет более важную роль по сравнению с другими науками. Все математические теоремы опираются на точные доказательства, основанные на выводе следствий из общепринятых общих математических аксиом или постулатов. Поэтому неудивительно, что ученые при анализе математических рассуждений открыли в этих рассуждениях больше всего схем (способов) правильного умозаключения.

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

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

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

Логическая наука сегодня – это сложное, системное знание, включающее в себя множество отраслей: логическая семиотика, символическая логика, диалектическая логика и др.

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

Источник