Основи алгоритмізації та програмування (Циммерман О.В.)

Закон, выражающий дистрибутивность (распределительность) одной данной логической или математической операции относительно другой данной операции. Примером этого закона может служить закон обычной арифметики: а (b + с) = аb + ас, выражающий распределительность умножения относительно сложения.

Формула закона:

.

.

1. Закон двойного отрицания (двойное отрицание исключает отрицание):

   А = .

• для логического сложения: А Ú B = B Ú A;

• для логического умножения: A & B = B & A.

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

• для логического сложения: (А Ú B) Ú C = A Ú (B Ú C);

• для логического умножения: (A & B) & C = A & (B & C).

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

• для логического сложения: (А Ú B) & C = (A & C) Ú (B & C);

• для логического умножения: (A & B) Ú C = (A Ú C) & (B Ú C).

Закон определяет правило выноса общего высказывания за скобку.

• для логического сложения: =  &;

• для логического умножения: =   Ú 

• для логического сложения: А Ú A = A;

• для логического умножения: A & A = A .

Закон означает отсутствие показателей степени.

• для логического сложения: А Ú 1 = 1, А Ú 0 = A;

• для логического умножения: A & 1 = A, A & 0 = 0.

• A &  = 0.

Невозможно, чтобы противоречащие высказывания были одновременно истинными.

• A Ú  = 1.

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

• для логического сложения: А Ú (A & B) = A;

• для логического умножения: A & (A Ú B) = A.

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

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

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

Упрощение формул.

Пример 1. Упростить формулу (А Ú В) & (А Ú С).

Решение:

Таким образом, мы доказали закон дистрибутивности.

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

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

Решение: 
 

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

В конструктивную математическую логику А. А. Марков вводит понятие «разрешимое высказывание» и связанное с ним понятие «прямое отрицание». В логике А. А. Маркова имеется и другой вид отрицания — усиленное отрицание, относящееся к так называемым полуразрешимым высказываниям.

Кроме материальной и усиленной импликации, при установ­лении истинности которых приходится заботиться об истинности посылки и заключения, А. А. Марков вводит дедуктивную имп­ликацию, определяемую по другому принципу. Дедуктивная имп­ликация «если А, то В»выражает возможность выведения В из А по фиксированным правилам, каждое из которых в применении к верным формулам даст верные формулы. Всякое высказывание, выводимое из истинного высказывания, будет истинным.

Через дедуктивную импликацию А. А. Марков определяет редукционное отрицание (reductio ad absurdum). Редукционное отрицание высказывания А (сформулированного на данном язы­ке) понимается как дедуктивная импликация «если А, то Л», где через Л обозначен абсурд. Это определение отрицания соответ­ствует обычной практике рассуждений математика: математик отрицает ту посылку, из которой вытекает абсурд. Для установ­ления истинности редукционного отрицания высказывания не требуется вникать в смысл этого высказывания. Высказывание, для которого установлена истинность редукционного отрицания, не может быть истинным.

Аристо́тель (др.-греч. Ἀριστοτέλης; 384 до н. э., Стагира, Фракия — 322 до н. э., Халкида, остров Эвбея) — древнегреческий философ. Ученик Платона. С 343 до н. э. — воспитатель Александра Македонского^[1]. В 335/4 г. до н. э.^[2] основал Ликей (др.-греч.Λύκειον Лицей, или перипатетическую школу). Натуралист классического периода. Наиболее влиятельный из философов древности; основоположник формальной логики. Создал понятийный аппарат, который до сих пор пронизывает философский лексикон и стиль научного мышления.

Аристотель был первым мыслителем, создавшим всестороннюю систему философии, охватившую все сферы человеческого развития: социологию, философию, политику, логику, физику. Его взгляды на онтологию имели серьёзное влияние на последующее развитие человеческой мысли. Метафизическое учение Аристотеля было принято Фомой Аквинским и развито схоластическим методом. Карл Маркс называл Аристотеля величайшим мыслителем древности^[3].

Го́тфрид Ви́льгельм Ле́йбниц 

саксонский философ, логик,математик, механик, физик, юрист, историк, дипломат, изобретатель и языковед. Основатель и первый президент Берлинской Академии наук, иностранный член Французской Академии наук^[13].

Важнейшие научные достижения:

• Лейбниц, независимо от Ньютона, создал математический анализ — дифференциальное и интегральное исчисления (см. исторический очерк), основанные на бесконечно малых^[13].
• Лейбниц создал комбинаторику как науку^[14].
• Он заложил основы математической логики^[5][8].
• Описал двоичную систему счисления с цифрами 0 и 1^[15].
• В механике ввёл понятие «живой силы» (прообраз современного понятия кинетической энергии) и сформулировалзакон сохранения энергии^[5].
• В психологии выдвинул понятие бессознательно «малых перцепций» и развил учение о бессознательной психической жизни^[5].

Лейбниц также является завершителем философии XVII века и предшественником немецкой классической философии, создателем философской системы, получившей название монадология^[16]. Он развил учение об анализе и синтезе^[5][17], впервые сформулировал закон достаточного основания (которому, однако, придавал не только логический (относящийся к мышлению), но и онтологический (относящийся к бытию) смысл: «… ни одно явление не может оказаться истинным или действительным, ни одно утверждение справедливым, — без достаточного основания, почему именно дело обстоит так, а не иначе…»)^[16][18]; Лейбниц является также автором современной формулировки закона тождества^[5][8][17]; он ввёл 

термин «модель»^[5], писал о возможности машинного моделирования функций человеческого мозга^[19]. Лейбниц высказал идею о превращении одних видов энергии в другие^[5], сформулировал один из важнейших вариационных принципов физики — «принцип наименьшего действия» — и сделал ряд открытий в специальных разделах физики^[5][8].

Он первым обратился к вопросу о возникновении российской правящей династии^[20], первым в немецкой историографии обратил внимание на взаимосвязь лингвистических проблем с генеалогией^[20], создал теорию исторического происхождения языков и дал их генеалогическую классификацию, явился одним из создателей немецкого философского и научного лексикона^[5][8].

Лейбниц также ввёл идею целостности органических систем, принцип несводимости органического к механическому и высказал мысль об эволюции Земли^[5].

Дави́д Ги́льберт (нем. David Hilbert; 23 янв

аря 1862 — 14 февраля 1943) — немецкий математик-универсал, внёс значительный вклад в развитие многих областей математики. В 1910—1920-е годы (после смерти Анри Пуанкаре) был признанным мировым лидером математиков. Гильберт разработал широкий спектр фундаментальных идей во многих областях математики, в том числе теорию инвариантов и аксиоматику евклидовой геометрии. Он сформулировал теорию гильбертовых пространств, одну из основ современного функционального анализа^[4].

Английский математик и логик. Профессор математики Королевского колледжа Корка с 1849 года. Один из основателей математической логики. Буль был, вероятно, первым после Джона Валлиса математиком, обратившимся к логической проблематике. Буль не считал логику разделом математики, но находил глубокую аналогию между символическим методом алгебры и символическим методом представления логических форм и силлогизмов.На математические темы Булем в течение жизни были созданы два систематических трактата: «Трактат о дифференциальных уравнениях» (1859; второе издание не завершено, материалы к нему опубликованы посмертно в 1865) и задуманный как его продолжение «Трактат о конечных разностях» (1860). Эти труды внесли важный вклад в соответствующие разделы математики и в то же время продемонстрировали глубокое понимание Булем философии своего предмета.

Визуальное программирование — способ создания программы для ЭВМ путём манипулирования графическими объектами вместо написания её текста.

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

 К первому поколению-  относят машинные языки — языки программирования на уровне команд процессора конкретной машины.

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

 Языки программирования четвёртого поколения (4GL) лучше представлять как среды разработки четвёртого поколения. Они относятся к временному периоду с 1970-х по начало 1990-х.

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

Дизъю́нкция (лат. disjunctio — разобщение), логи́ческое сложе́ние, логи́ческое ИЛИ, включа́ющее ИЛИ; иногда просто ИЛИ — логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу»

|| b,a{\displaystyle b,\;a} | b,a ORb{\displaystyle b,\;a~{\mbox{OR}}\,\,b},max(a,b).{\displaystyle ,\;\max(a,b).}

Эквивалентность - это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.

Таблица истинности для эквивалентности

Бинарная логическая операция,  булева функция над двумя переменными. Введена в рассмотрение Генри Шеффером в 1913 г. Штрих Шеффера, обычно обозначаемый |, эквивалентен операции И-НЕ.

Таким образом, высказывание X | Y означает, что X и Y несовместны, то есть не являются истинными одновременно. От перемены мест операндов результат операции не изменяется.

Задаётся следующей таблицей истинности:

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

Обеспечение доступности главного, выделение основного содержания путём помещения всего мешающего, второстепенного в некую условную капсулу

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

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

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

Высказывание - это повествовательное предложение, про которое можно определенно сказать истинно оно или ложно (истина (логическая 1), ложь (логический 0)).

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

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

Дискре́тность (от лат. discretus — разделённый, прерывистый) — свойство, противопоставляемое непрерывности, прерывность.

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

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

Трансля́тор — программа или техническое средство, выполняющее трансляцию программы^[1][2].

Вложенный цикл - это цикл, размещённый внутри другого цикла.

Логическое выражение в программировании — конструкция языка программирования, результатом вычисления которой является «истина» или «ложь».

Некоторая величина, не изменяющая своё значение в рамках рассматриваемого процесса.

 наименьшая автономная часть языка программирования; команда;

Active Oberon — типобезопасный модульный объектно-ориентированный многопоточный язык программирования общего назначения, разработанный в 1996 — 1997 гг. группой проф. Гуткнехта^[de] в Швейцарской высшей технической школе Цюриха (ETHZ) с целью введения в язык Оберон свойств для выражения параллелизма посредством активных объектов^[2

C++ — компилируемый, статически типизированный язык программирования общего назначения.

Поддерживает такие парадигмы программирования, как процедурное программирование, объектно-ориентированное программирование, обобщённое программирование, обеспечивает модульность, раздельную компиляцию, обработку исключений, абстракцию данных, объявление типов (классов) объектов, виртуальные функции. Стандартная библиотека включает, в том числе, общеупотребительные контейнеры и алгоритмы. C++ сочетает свойства как высокоуровневых, так и низкоуровневых языков.^[1][2] В сравнении с его предшественником — языком C, — наибольшее внимание уделено поддержкеобъектно-ориентированного и обобщённого программирования.^[2]

HTML (от англ. HyperText Markup Language — «язык гипертекстовой разметки») — стандартизированный язык разметки документов во Всемирной паутине. Большинство веб-страниц содержат описание разметки на языке HTML (или XHTML). Язык HTML интерпретируется браузерами; полученный в результате интерпретации форматированный текст отображается на экране монитора компьютера или мобильного устройства.

Лисп (LISP, от англ. LISt Processing language — «язык обработки списков»; современное написание: Lisp) — семейство языков программирования, программы и данные в которых представляются системамилинейных списков символов. Создатель Лиспа Джон Маккарти занимался исследованиями в области искусственного интеллекта (в дальнейшем ИИ) и созданный им язык по сию пору является одним из основных средств моделирования различных аспектов ИИ.

Это один из старейших (наряду с Фортраном и Коболом) используемых по сей день высокоуровневых языков программирования^[1], а также первый из сохранившихся в использовании языков, использующих автоматическое управление памятью и сборку мусора^[2].

Традиционный Лисп имеет динамическую систему типов. Язык является функциональным, но начиная уже с ранних версий обладает также чертами императивности, к тому же, имея полноценные средствасимвольной обработки, позволяет реализовать объектно-ориентированность; примером такой реализации является платформа CLOS.

Является языком системного программирования для так называемых лисп-машин, производившихся в 1980-е годы, например, фирмой Symbolics^[en].

Наряду с языком Ада, Лисп прошёл процесс фундаментальной стандартизации для использования в военном деле и промышленности, в результате чего появился стандарт Common Lisp. Его реализации существуют для большинства платформ.

Object Pascal (с англ. — «Объектный Паскаль») — язык программирования, разработанный в фирме Apple Computer в 1986 годугруппой Ларри Теслера, который консультировался с Никлаусом Виртом. Произошёл от более ранней объектно-ориентированной версии Паскаль^[2], называвшейся Clascal, который был доступен на компьютере Apple Lisa.

PHP – это широко используемый язык сценариев общего назначения с открытым исходным кодом. Говоря проще, PHP это язык программирования, специально разработанный для написания web-приложений (сценариев), исполняющихся на Web-сервере. Аббревиатура PHP означает “Hypertext Preprocessor (Препроцессор Гипертекста)".

Паскаль (англ. Pascal) — один из наиболее известных языков программирования^[5], используется для обучения программированию в старших классах и на первых курсах вузов, является базой для ряда других языков.

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

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