Что изучает логика информатика

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

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Урок по информатике «Основы логики»

Формы организации урока: объяснительно-иллюстративный, диалогический.

Ход урока.

I. Изложение нового материала.

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

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

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

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

2. Формы мышления.

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

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

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

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

Упражнение 1 (устно). Приведите свои примеры.

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

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

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

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

Упражнение 2 (устно)

1. Перечислите существенные признаки, составляющие содержание понятий: добродетель, истинна, ложь.
2. Определите объем понятий: столица России, столица, река.

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

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

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

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

Упражнение 3 (устно). Объясните, почему следующие высказывания не являются высказываниями:

1. Какого цвета твой велосипед?
2. Число Х больше пяти?
3. 5Х-2
4. Посмотрите в окно.
5. Пейте томатный сок!
6. Вы были в музее?
7. Разность чисел 12 и Х равна 6.

Упражнение 4 (устно). Какие из следующих высказываний являются истинными, а какие ложными?

1. Город Москва – столица России.
2. Число 12 – простое.
3. 7*3=1.
4. 12

1. Все металлы – простые вещества. Литий – простое вещество.	2. Все школьники – отличники. Упражнение 6. 1. Дано высказывание “Все углы равнобедренного треугольника равны”. Путем умозаключений получить высказывание “Этот треугольник равносторонний”. 2. Оцените правильность следующего рассуждения: сидящий встал; кто встал, тот стоит; значит, сидящий стоит. 3. Алгебра высказываний. Алгебра высказываний была разработана для того, чтобы можно было определять истинность или ложность составного высказывания, не вникая в их содержание. Опр.5 Алгебра логики (алгебра высказываний) – раздел математической логики, изучающий строение (форму, структуру) сложных логических высказываний и способы установления их истинности с помощью алгебраических методов. Под высказыванием (суждением) будем понимать повествовательное предложение, относительно которого можно сказать, истинно или ложно. В алгебре высказываний простым высказываниям ставятся в соответствии логические переменные, обозначаемые прописными буквами латинского алфавита. А= “Листва на деревьях опадает осенью”. В= “Земля прямоугольная”. Опр.6 В алгебре высказываний высказывания обозначаются именами логических переменных, которые могут принимать лишь два значения: “истинна” (1) и “ложь” (0). В алгебре высказываний над высказываниями можно производить логические операции, в результате которых получаются новые, составные (сложные) высказывания. Опр.7 Логическая операция – способ построения сложного высказывания из данных высказываний, при котором значение истинности сложного высказывания полностью определяется значениями истинности исходных высказываний. Рассмотрим три базовых логических операций – инверсию, конъюнкцию, дизъюнкцию и дополнительные – импликацию и эквивалентность. Логическая операция Название Соответствует союзу Обозначение знаками Таблица истинности Логическая операция Инверсия (от лат. inversion – переворачиваю)	отрицание	не А		Опр. 8 Инверсия логической переменной истина, если переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.
Конъюнкция (от лат. conjunction – связываю)	Логическое умножение	А и В		Опр.9Конъюнкция двух логических переменных истинна тогда и только тогда, когда оба высказывания, истинны.
Дизъюнкция (от лат. disjunction – различаю)	Логическое сложение	А или В		Опр. 10 Дизъюнкция двух логических переменных ложна тогда и только тогда, когда оба высказывания ложны.
Импликация (от лат. implication – тесно связывать)	Логическое следование	Если А, Когда А, тогда В		Опр. 12 Эквивалентность двух логических переменных истинна тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны

Упражнение 7. Даны два простых высказывания:

А= “Щука – рыба”;
В=“Ворона – певчая птица”.

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

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

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

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

Упражнение 8.

Дана формула . Определите порядок вычисления.

II. Закрепление изученного материала.

4. По данным формам сложных высказываний запишите высказывания на русском языке.

1.
2.
3.
4.
5.

6. Даны два высказывания: А = “2 х 2 = 4”, В = “2 х 2 = 5”. Очевидно, что А=1, В=0. Какие из высказываний истинны?

а)
б)
в) А
г)
д)
е)

Источник

Теоретический материал к теме «Основы логики» курса информатики

«Управление общеобразовательной организацией:
новые тенденции и современные технологии»

Свидетельство и скидка на обучение каждому участнику

ОСНОВЫ ЛОГИКИ
Методические указания
к темам курса информатики

1. Понятие о логике как о науке. Практическое приложение логики.

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

закон, порядок, слово, понятие, рассуждение, разум, сын Божий и др.

Оттачивая искусство одерживать верх в дискуссиях собеседников, в судебных тяжбах, логика за историю своего развития прошла несколько этапов (общая (традиционная, аристотелева), символическая (математическая) и т.д.). Наиболее интересным и выгодным приложением достижений математической логики к практическим нуждам людей стало создание счётно-решающих устройств, электронных вычислительных машин. Человек сумел познать наиболее общие, присущие всем людям законы мышления и смоделировать работу своего мозга, «вручив» частично функции вычислений и умозаключений сложным техническим неживым устройствам.

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

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

Если мы скажем, что “то, что мы видим, ощущаем, и есть внешний мир”, что «внешний мир именно такой, каким мы его воспринимаем», то из этого следует, что Земля плоская, а Солнце вращается вокруг неё. В самом деле, фотография Земли из космоса свидетельствует, что земной диск плоский. Тогда земной глобус станет моделью плоской Земли, картой земного диска, для удобства обозрения спроецированной на сферу с подставкой. Кроме того, микробов и вирусов, молекул и атомов, подлости и совести нет, так как их не видно. И такие нелепые выводы следуют из первоначального решения о том, что реальный мир и его образ одно и то же.

Представим, что четыре радиолокационные станции обнаружили в небе над страной, которую они прикрывают, самолёт-шпион. Пусть каждая РЛС сообщила своим управляющим структурам об этом самолёте. Если каждая управляющая структура сообщит главнокомандующему страны о замеченном самолёте, то президент получит четыре разных сообщения из четырёх разных источников. Значит ли это, что и самолётов обнаружено четыре? Если да, то мы всё ещё заблуждаемся, что «сам мир и его образ в нашей голове – одно и то же». Более достоверным же будет ответ, что сам внешний мир (источник образа) и образ мира, отражение мира в головах людей различные вещи. Приведём сравнительную таблицу внизу:

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

Есть правильные мысли. Они истинны, т.е. соответствуют дейст-вительности, своим объек-там.

Есть ложные мысли, они сознательно (умышленно) искажают действитель-ность.

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

Не все выражения естественных языков являются высказываниями:

1. ППП, высказывающееся о самом себе:

2. Риторический вопрос: суждение выражается в грамматической форме вопроса, ответ на который подразумевается заранее известным :

“ Ребята! Не Москва ль за нами?”

2. Любой вопрос, исключая риторический.

“ Как пройти в библиотеку?”

3. Восклицательное предложение:

“ Как хороши, как свежи были розы!”

3. Побудительное предложение (приказ, императив): “Пшёл вон!”

“ Говори кратко. Проси мало. Уходи быстро.” (Пётр I).

В учебниках информатики логические величины определяются более формально:

«логическое значение пропозициональной переменной» (её состояние – И стинность или Л ожность, логическая 1 или логический 0 );

«логическая переменная» (операнд, то с чем работает оператор);

«логический оператор» (то, что обрабатывает операнды).

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

4.Импликация (условный оператор)

5. Логическое равенство (эквиваленция)

2. Символическая логика. Семантика логических операторов.

2.1. Оператор инверсии (отрицания).

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

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

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

Для инверсии (отрицания) семантическая таблица строится так:

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

В русском языке правило вычёркивания можно применять к предложениям: ведь сказать «Он держал себя не без достоинства» то же самое, что сказать «Он держался достойно». В содержательном плане инверсии соответствует вывернутая рубашка, обманутый обманщик. Так, на карнавале можно делать всё, что нельзя в будние дни.

Следует помнить, что в логике высказываний субъектно-предикатная структура суждений игнорируется, и отрицание должно применяться ко всему высказыванию, а не к его частям. Если неверно (ложно) утверждение «Верно, что все розы красные», то истинно (верно) только утверждение « НЕ верно, что все розы красные». Утверждение «Все розы НЕ красные» также будет ложно, поскольку в таком высказывании отрицается лишь предикат суждения, а должно инвертироваться всё высказывание как единое целое.

В описании работы технических устройств (аппаратной реализации логических контуров) семантические таблицы заполняются по правилам, описанным выше, за одним исключением: заполнение логических значений переменной идёт сверху вниз от логических нолей к логическим единицам. Следовательно, матрица семантической таблицы инверсии будет выглядеть иначе (сравните таблицы на этой и следующей страницах). Оба способа записи (И/Л-

таблица и 1\0-таблица) идентичны друг другу, но матрица логических значений одного «опрокинута» для другого.

зелёные яблоки + НЕ зелёные яблоки = ЯБЛОКИ

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

Если на вход а слева поступает импульс 1, то на выходе (справа) будет получен сигнал 0. И наоборот, если на вход поступит сигнал 0, на выходе инвертор выдаст сигнал 1. Таблица возможных состояний инвертора на входе и выходе приведена справа.

2.2. Оператор логического умножения (конъюнкция, логическое «И»).

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

Составим семантическую таблицу для логического умножения. Пусть

а = «Жених явился»; b – «Невеста явилась»; a & b = ab = «Брак возможен». Заполнение семантической таблицы для конъюнкции по сравнению с оператором инверсии будет более сложным. В операции участвуют два операнда, у каждого может быть два состояния, стало быть, надо рассмотреть все их возможные сочетания по истине и лжи. Если заменить логические значения наличием или отсутствием фигурок жениха или невесты в соответствующих столбцах, получим идентичные по смыслу табличные записи. В отечественной традиции логическое умножение пишется заглавной греческой «лямбдой» (), применим эту запись к И/Л-таблице. В учебной литературе конъюнкция чаще обозначается амперсендом (&), применим такую запись к 1\0-таблице.

Источник

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

Содержание

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

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

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

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

Логика в программировании

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

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

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

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

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

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

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

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

Логика и искусственный интеллект

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

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

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

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

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

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

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

Логика и логическое программирование

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

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

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

Логика в базах данных

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

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

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

Поиск информации в реляционных базах данных проводится с помощью языка запросов SQL (англ. Structured Query Language — язык структурированных запросов) — универсальный компьютерный язык, применяемый для создания, поиска и модификации информации в базах данных.

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

Источник