Въз основа на: демо Опции за единен държавен изпитпо информатика за 2015 г. по учебника на Людмила Леонидовна Босова

В предишната част 1 обсъдихме с вас логическите операции Disjunction и Conjunction, всичко, което ни остава, е да анализираме инверсията и да преминем към решаване на задачата за Единен държавен изпит.

Инверсия

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

Следните символи се използват за запис на инверсия: NOT, `¯`, ` ¬ `

Дефинирана е инверсия следната таблицаистина:

Инверсията иначе се нарича логическо отрицание.

Всяко сложно твърдение може да бъде написано във формата логически израз — изрази, съдържащи логически променливи, знаци за логически оператори и скоби. Логическите операции в логически израз се извършват в следния ред: инверсия, конюнкция, дизюнкция. Можете да промените реда на операциите, като използвате скоби.

Логическите операции имат следния приоритет: инверсия, конюнкция, дизюнкция.

И така, пред нас е задача № 2 от Единния държавен изпит по информатика 2015 г

Александра попълваше истинската таблица за израза F. Тя успя да попълни само малък фрагмент от таблицата:

x1	x2	x3	x4	x5	x6	x7	x8	Е
	0						1	0
1			0					1
			1				1	1

Какъв израз може да бъде F?

Това, което прави решаването на проблема много по-лесно е, че във всяка версия на сложния израз F има само една логическа операция: умножение или събиране. В случай на умножение /\ ако поне една променлива е равна на нула, тогава стойността на целия израз F също трябва да е равна на нула. И в случай на добавяне V, ако поне една променлива е равна на единица, тогава стойността на целия израз F трябва да бъде равна на 1.

Данните в таблицата за всяка от 8-те променливи на израза F са напълно достатъчни, за да ги решим.

Нека проверим израз номер 1:

• ? /\ 1 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 0 )
• от втория ред на таблицата x1=1, x4=0 виждаме, че F е възможно и може да бъде равно на = 1, ако всички други променливи са равни на 1 (1 /\ ? /\ ? /\ 1 /\ ? /\ ? /\ ? /\ ? )
• според третия ред на таблицата x4=1, x8=1 виждаме, че F=0 (? /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ 0 ), а в таблицата имаме F=1, което означава, че израз номер едно е за нас КАТЕГОРИЧНО НЕ Е ПОДХОДЯЩ.

Нека проверим израз номер 2:

• от първия ред на таблицата x2=0, x8=1 виждаме, че F е възможно и може да бъде равно на = 0, ако всички други променливи са равни на 0 (? V 0 V ? V ? V ? V ? V ? V 0 )
• от втория ред на таблицата x1=1, x4=0 виждаме, че F = 1 ( 1 V ? V ? V 1 V ? V ? V ? V ? )
• според третия ред на таблицата x4=1, x8=1 виждаме, че F е възможно и може да бъде равно на = 1, ако поне една от останалите променливи е равна на 1 ( ? V ? V ? V 0 V ? V ? V ? V 0 )
  

Нека проверим израз номер 3:

• от първия ред на таблицата x2=0, x8=1 виждаме, че F=0 (? /\ 0 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 1 )
• от втория ред на таблицата x1=1, x4=0 виждаме, че F =0 (0 /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ ? ), а в таблицата имаме F=1 и това означава, че израз номер три ни дава КАТЕГОРИЧНО НЕ Е ПОДХОДЯЩ.

Нека проверим израз номер 4:

• от първия ред на таблицата x2=0, x8=1 виждаме, че F=1 ( ? V 1 V ? V ? V ? V ? V ? V 0 ), а в таблицата имаме F=0 и това означава, че израз номер четири ни дава КАТЕГОРИЧНО НЕ Е ПОДХОДЯЩ.

Когато решавате задача на единния държавен изпит, трябва да направите точно същото: отхвърлете тези опции, които определено не са подходящи въз основа на данните в таблицата. оставащи възможен вариант(както в нашия случай, вариант номер 2) ще бъде правилният отговор.

Проблемът за определяне на истинността на израза е изправен пред много науки. Всяка доказателствена дисциплина трябва да се основава на определени критерии за истинност на доказателствата. Науката, която изучава тези критерии, се нарича алгебра на логиката. Основният постулат на алгебрата на логиката е, че всяко най-богато украсено твърдение може да бъде представено като алгебричен израз на по-прости твърдения, чиято истинност или лъжа е лесно да се определи.

За всяка „алгебрична“ операция върху дадено твърдение се определя правило за определяне на истинността или неистинността на модифицираното твърдение въз основа на истинността или неистинността на оригиналното твърдение. Тези правила са написани чрез таблици за истинност на израза. Преди да съставите таблици на истината, трябва да се запознаете по-добре с алгебрата на логиката.

Алгебрични трансформации на логически изрази

Всеки логически израз, както и неговите променливи (изявления), приемат две стойности: лъжа или истина. Лъжата се означава с нула, а истината с единица. След като сме разбрали областта на дефиницията и обхвата на приемливите стойности, можем да разгледаме операциите на алгебрата на логиката.

Отрицание

Отрицание и инверсия- най-простата логическа трансформация. Съответства на частицата "не". Тази трансформация просто обръща твърдението. Съответно значението на твърдението също се променя на обратното. Ако твърдение А е вярно, тогава "не А" е невярно. Например твърдението „прав ъгъл е ъгъл, равен на деветдесет градуса“ е вярно. Тогава неговото отричане "прав ъгъл не е равен на деветдесет градуса" е лъжа.

Таблица на истината за отрицаниеще бъде така:

Дизюнкция

Тази операция може да бъде обикновени или строги, техните резултати ще варират.

Обичайната дизюнкция или логическо добавяне съответства на връзката "или". То ще е вярно, ако поне едно от твърденията, включени в него, е вярно. Например изразът „Земята е кръгла или стои на три стълба“ ще бъде верен, тъй като първото твърдение е вярно, въпреки че второто е невярно. В таблицата ще изглежда така:

Строга дизюнкция или събиране по модул също се нарича "изключително или". Тази операция може да бъде под формата на граматична конструкция „едно от две: или... или...“. Тук стойността на логически израз ще бъде невярна, ако всички твърдения, включени в него, имат една и съща истина. Тоест и двете твърдения са или заедно верни, или заедно невярни.

Таблица на изключителни или

Импликация и еквивалентност

Изводът е следствиеи може да се изрази граматически като „от А следва Б“. Тук твърдение A ще се нарече предпоставка, а B ще се нарече следствие. Една импликация може да бъде невярна само в един случай: ако предпоставката е вярна и следствието е невярно. Тоест от истината не може да произтича лъжа. Във всички останали случаи внушението е вярно. Вариантите, когато и двете твърдения имат една и съща истина, не повдигат въпроси. Но защо истинско следствие от фалшива предпоставка е вярно? Въпросът е, че всичко може да последва от фалшива предпоставка. Това е, което отличава импликацията от еквивалентността.

В математиката (и други демонстративни дисциплини) импликацията се използва за определяне на необходимо условие. Например твърдение A е „точка O е екстремумът на непрекъсната функция“, твърдение B е „производната на непрекъсната функция в точка O става нула“. Ако O наистина е точката на екстремума на непрекъсната функция, тогава производната в тази точка наистина ще бъде равна на нула. Ако O не е точка на екстремум, тогава производната в тази точка може или не може да бъде нула. Тоест B е необходимо за A, но не е достатъчно.

Таблица на истината за импликацияизглежда така:

Логическата операция на еквивалентността е по същество взаимно внушение. „А е еквивалентно на B“ означава, че „от A следва B“ и „от B следва A“ едновременно. Еквивалентността е вярна, когато и двете твърдения са или едновременно верни, или едновременно неверни.

В математиката еквивалентността се използва за определяне на необходимо и достатъчно условие. Например твърдение A - „Точка O е точката на екстремум на непрекъсната функция“, твърдение B - „В точка O производната на функцията става нула и променя знака.“ Тези две твърдения са еквивалентни. B съдържа необходимо и достатъчно условие за A. Обърнете внимание, че в в този примеризявления B всъщност е връзка на две други: „производната в точка O става нула“ и „производната в точка O променя знака“.

Други логически функции

По-горе обсъдихме основните логически операции, които често се използват. Има и други функции, които се използват:

• Ударът на Шефер или несъвместимостта е отрицанието на връзката на А и Б
• Стрелката на Пърс представлява провала на отрицанието на дизюнкцията.

Изграждане на таблици на истинност

За да изградите таблица на истината за всеки логически израз, трябва да действате в съответствие с алгоритъма:

1. Разбийте израза на прости изрази и маркирайте всеки като променлива.
2. Дефинирайте логически трансформации.
3. Определете реда на тези трансформации.
4. Пребройте редовете в бъдещата таблица. Техният брой е равен на две на степен N, където N е броят на променливите, плюс един ред за заглавката на таблицата.
5. Определете броя на колоните. Той е равен на сумата от броя на променливите и броя на действията. Можете да представите резултата от всяко действие като нова променлива, ако това има смисъл.
6. Заглавието се попълва последователно, първо всички променливи, след това резултатите от действията в реда, в който са извършени.
7. Трябва да започнете да попълвате таблицата с първата променлива. За нея броят на линиите е разделен наполовина. Едната половина е запълнена с нули, втората с единици.
8. За всяка следваща променлива нули и единици се редуват два пъти по-често.
9. Така се попълват всички колони с променливи и за последната променлива стойностпромени на всеки ред.
10. След това последователно се попълват резултатите от всички действия.

В резултат на това последната колона ще покаже стойността на целия израз в зависимост от стойността на променливите.

Специално трябва да се спомене за ред на логически действия. Как да го дефинираме? Тук, както и в алгебрата, има правила, които определят последователността на действията. Те се изпълняват в следния ред:

1. изрази в скоби;
2. отрицание или инверсия;
3. връзка;
4. строга и обикновена дизюнкция;
5. импликация;
6. еквивалентност.

Примери

За да консолидирате материала, можете да опитате да създадете таблица на истината за споменатите по-горе логически изрази. Нека да разгледаме три примера:

• Инсулт на Шефър.
• Стрелата на Пиърс.
• Определение за еквивалентност.

Инсулт на Шефър

Щрихът на Schaeffer е булев израз, който може да бъде написан като "не (A и B)". Има две променливи и две действия. Съюзът е в скоби, което означава, че се изпълнява първи. Таблицата ще има заглавка и четири реда с променливи стойности, както и четири колони. Да попълним таблицата:

Отрицанието на конюнкция изглежда като дизюнкция на отрицания. Това може да се провери чрез конструиране на таблица на истината за израза „не A или не B“. Направете това сами и имайте предвид, че тук вече ще има три операции.

Стрелата на Пиърс

Имайки предвид стрелката на Пърс, която представлява отрицанието на дизюнкцията "не (A или B)", нека я сравним с връзката на отрицанията "не A и не B". Нека попълним две таблици:

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

Определение за еквивалентност

Можем да кажем за твърдения A и B, че те са еквивалентни тогава и само ако A следва от B и B следва от A. Нека напишем това като логически израз и изградим таблица на истинност за него. „(A е еквивалентно на B) е еквивалентно на (от A следва B) и (от B следва A).“

Има две променливи и пет действия. Изграждаме масата:

Всички стойности в последната колона са верни. Това означава, че горното определение за еквивалентност е вярно за всякакви стойности на A и B. Това означава, че винаги е вярно. точно така използвайки таблица на истинатаможете да проверите правилността на всякакви дефиниции и логически конструкции.

Продължителност на урока: 45 мин

Тип урок:комбиниран:

• проверка на знанията – устна работа;
• нов материал – лекция;
• затвърдяване – практически упражнения;
• проверка на знанията – задачи за самостоятелна работа.

Цели на урока:

• дайте концепцията за таблица на истината;
• затвърдяване на материала от предишния урок „Алгебра на твърденията”;
• използване информационни технологии;
• внушаване на умение за самостоятелно търсене на нов материал;
• развитие на любопитство и инициативност;
• възпитание на информационна култура.

План на урока:

1. Организационен момент (2 мин.).
2. Повторение на материала от предишния урок (устен въпрос) (4 минути).
3. Обяснение на нов материал (12 минути).
4. Консолидация

• казус (5 мин.);
• практически упражнения (10 мин.);
• задачи за самостоятелна работа (10 мин).

Оборудване и софтуерни материали:

• бяла дъска;
• мултимедиен проектор;
• компютри;
• редактор на презентации MS PowerPoint 2003;
• справочни материали за раздаване „Таблици на истината“;
• Демонстрация на презентацията „Таблица на истината“.

Напредък на урока

I. Организационен момент

Продължаваме да изучаваме темата „Основи на логиката“. В предишните уроци видяхме, че логиката е доста тясно свързана с нашето ежедневие и също така видяхме, че почти всяко твърдение може да бъде написано като формула.

II. Повторение на материала от предишния урок

Нека си припомним основните определения и понятия:

III. Обяснение на нов материал

Последните два примера се отнасят за сложни твърдения. Как да определим истинността на сложни твърдения?

Казахме, че е изчислено. За тази цел в логиката има таблици за изчисляване на истинността на съставни (комплексни) твърдения. Те се наричат ​​таблици на истината.

И така, темата на урока е ТАБЛИЦИТЕ НА ИСТИНАТА.

3.1) Определение.Таблица на истината е таблица, показваща истинността на сложно твърдение за всички възможни стойности на входните променливи (Фигура 1).

3.2) Нека разгледаме по-подробно всяка логическа операция в съответствие с нейната дефиниция:

1. Инверсия (отрицание) е логическа операция, която свързва всяко просто изявление със съставно изявление, което означава, че оригиналното изявление се отрича.

Тази операция се прилага само за една променлива, така че само двелинии, защото една променлива може да има едно от двестойности: 0 или 1.

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

Лесно се вижда, че тази таблица наистина е подобна на таблица за умножение.

3. Дизюнкция (събиране) е логическа операция, която свързва всеки две прости твърдения със съставно твърдение, което е невярно тогава и само ако и двете начални твърдения са неверни.

Можете да се уверите, че таблицата е подобна на таблицата за добавяне, с изключение на последната стъпка. В двоичната бройна система 1 + 1 = 10, в десетичната – 1 + 1 = 2. В логиката стойността на променлива 2 е невъзможна, нека разгледаме 10 от гледна точка на логиката: 1 – вярно, 0 – невярно, т.е. 10 е вярно и невярно едновременно, което не може да бъде, така че последното действие е строго базирано на дефиницията.

4. Импликация (следване) е логическа операция, която свързва всеки две прости твърдения със съставно твърдение, което е невярно, ако и само ако условието е вярно и следствието е невярно.

5. Еквивалентност (еквивалентност) е логическа операция, която свързва всеки две прости твърдения със съставно твърдение, което е вярно тогава и само ако и двете първоначални твърдения са едновременно верни или неверни.

Последните две операции бяха обсъдени от нас в предишния урок.

3.3) Нека да го разгледаме алгоритъм на таблицата на истинатаза сложно изявление:

3.4) Разгледайте пример за съставяне на таблица на истината за сложно твърдение:

Пример. Постройте таблица на истинност за формулата: A U B -> ¬A U C.

Решение (Фигура 2)

Примерът показва, че таблицата на истината не е цялото решение, а само последното действие (колоната, маркирана в червено).

IV. Консолидация.

За да консолидирате материала, от вас се иска самостоятелно да решите примерите под буквите a, b, c и допълнително d–g (Фигура 3).

V. домашна работа, обобщение на материала.

Домашната работа също ви се дава на екрана на монитора (Фигура 4)

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

Определение 1

Логическа функция– функция, чиито променливи приемат една от двете стойности: $1$ или $0$.

Всяка логическа функция може да бъде определена с помощта на таблица на истината: наборът от всички възможни аргументи е написан от лявата страна на таблицата, а съответните стойности на логическата функция са записани от дясната страна.

Определение 2

Таблица на истината– таблица, която показва какви стойности ще приеме съставен израз за всички възможни набори от стойности на простите изрази, включени в него.

Определение 3

Еквивалентсе наричат ​​логически изрази, чиито последни колони от таблици на истинност съвпадат. Еквивалентността се обозначава със знака $«=»$.

Когато съставяте таблица на истината, е важно да вземете предвид следния ред на логически операции:

Фигура 1.

Скобите имат предимство при изпълнение на реда на операциите.

Алгоритъм за построяване на таблица на истинност на логическа функция

Определете броя на редовете: брой редове= $2^n + 1$ (за заглавния ред), $n$ – брой прости изрази. Например за функции на две променливи има $2^2 = 4$ комбинации от набори от стойности на променливи, за функции на три променливи има $2^3 = 8$ и т.н.

Определете броя на колоните: брой колони = брой променливи + брой логически операции.При определяне на броя на логическите операции се взема предвид и редът на тяхното изпълнение.

Попълнете колоните с резултатите от логическите операциив определена последователност, като се вземат предвид таблиците на истинност на основните логически операции.

Фигура 2.

Пример 1

Създайте таблица на истинност за логическия израз $D=\bar(A) \vee (B \vee C)$.

Решение:

Да определим броя на редовете:

брой редове = $2^3 + 1=9$.

Брой променливи – $3$.

1. обратен ($\bar(A)$);
2. дизюнкция, т.к то е в скоби ($B \vee C$);

3. дизюнкция ($\overline(A)\vee \left(B\vee C\right)$) е необходимият логически израз.

   Брой колони = $3 + 3=6$.

Нека попълним таблицата, като вземем предвид таблиците за истинност на логическите операции.

Фигура 3.

Пример 2

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

Решение:

Да определим броя на редовете:

Броят на простите изрази е $n=3$, което означава

брой редове = $2^3 + 1=9$.

Нека да определим броя на колоните:

Брой променливи – $3$.

Брой логически операции и тяхната последователност:

1. отрицание ($\bar(C)$);
2. дизюнкция, т.к то е в скоби ($A \vee B$);
3. връзка ($(A\vee B)\bigwedge \overline(C)$);
4. отрицание, което означаваме с $F_1$ ($\overline((A\vee B)\bigwedge \overline(C))$);
5. дизюнкция ($A \vee C$);
6. връзка ($(A\vee C)\bigwedge B$);
7. отрицание, което означаваме с $F_2$ ($\overline((A\vee C)\bigwedge B)$);

8. дизюнкция е желаната логическа функция ($\overline((A\vee B)\bigwedge \overline(C))\vee \overline((A\vee C)\bigwedge B)$).

Инструкции. Когато въвеждате от клавиатурата, използвайте следните обозначения: Например, логическият израз abc+ab~c+a~bc трябва да бъде въведен така: a*b*c+a*b=c+a=b*c
За да въведете данни под формата на логическа диаграма, използвайте тази услуга.

Правила за въвеждане на логическа функция

1. Вместо символа v (дизюнкция, ИЛИ), използвайте знака +.
2. Не е необходимо да се указва обозначение на функция преди логическа функция. Например, вместо F(x,y)=(x|y)=(x^y) трябва просто да въведете (x|y)=(x^y) .
3. Максималният брой променливи е 10.

Проектирането и анализът на компютърни логически схеми се извършва с помощта на специален клон на математиката - логическата алгебра. В алгебрата на логиката могат да се разграничат три основни логически функции: „НЕ“ (отрицание), „И“ (конюнкция), „ИЛИ“ (дизюнкция).
За да се създаде всяко логическо устройство, е необходимо да се определи зависимостта на всяка от изходните променливи от съществуващите входни променливи; тази зависимост се нарича превключваща функция или функция на логическата алгебра.
Функция на логическата алгебра се нарича напълно дефинирана, ако са дадени всички 2n от нейните стойности, където n е броят на изходните променливи.
Ако не всички стойности са дефинирани, функцията се нарича частично дефинирана.
Едно устройство се нарича логическо, ако неговото състояние е описано с помощта на функция на логическата алгебра.
Следните методи се използват за представяне на функция на логическата алгебра:

• словесното описание е форма, която се използва в началния етап на проектиране и има условно представяне.
• описание на функция на логическата алгебра под формата на таблица на истинност.
• описание на функция на логическата алгебра под формата на алгебричен израз: използват се две алгебрични форми на FAL:
  а) DNF – дизюнктивна нормална формае логическата сума на елементарните логически продукти. DNF се получава от таблицата на истината, като се използва следният алгоритъм или правило:
  1) в таблицата са избрани онези редове от променливи, за които изходната функция е =1.
  2) за всеки ред от променливи се записва логически продукт; Освен това променливи =0 се записват с инверсия.
  3) полученият продукт се сумира логически.
  Fdnf= X 1 *X 2 *X 3 ∨ X 1 x 2 X 3 ∨ X 1 X 2 x 3 ∨ X 1 X 2 X 3
  Казва се, че DNF е перфектен, ако всички променливи имат еднакъв ранг или ред, т.е. Всяка работа трябва да включва всички променливи в пряка или обратна форма.
  б) CNF – конюнктивна нормална формае логическо произведение на елементарни логически суми.
  CNF може да се получи от таблицата на истината, като се използва следният алгоритъм:
  1) изберете набори от променливи, за които изходната функция е =0
  2) за всеки набор от променливи записваме елементарна логическа сума, а променливите =1 се записват с инверсия.
  3) получените суми се умножават логически.
  Fsknf=(X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3)
  CNF се нарича перфектен, ако всички променливи имат еднакъв ранг.

Фигура 1 - Схема на логическо устройство

Дефинирани са всички операции на алгебрата на логиката таблици на истинатаценности. Таблицата на истината определя резултата от операция за всеки е възможен x логически стойности на оригиналните изрази. Броят на опциите, отразяващи резултата от прилагането на операции, ще зависи от броя на изразите в логическия израз. Ако броят на изявленията в логическия израз е N, тогава таблицата на истината ще съдържа 2 N реда, тъй като има 2 N различни комбинации от възможни стойности на аргументи.

Операция НЕ - логическо отрицание (инверсия)

• ако оригиналният израз е верен, тогава резултатът от неговото отрицание ще бъде фалшив;
• ако оригиналният израз е фалшив, тогава резултатът от неговото отрицание ще бъде верен.

Операция ИЛИ - логическо събиране (дизюнкция, обединение)

Операция И - логическо умножение (конюнкция)

Операция “АКО-ТОГАВА” - логическо следствие (импликация)

Операция „A ако и само ако B“ (еквивалентност, еквивалентност)

Операция „Добавяне по модул 2“ (XOR, изключителна или стриктна дизюнкция)

Приоритет на логическите операции

• Действия в скоби
• Инверсия
• Съюз (&)
• Дизюнкция (V), Изключително ИЛИ (XOR), сума по модул 2
• Извод (→)
• Еквивалентност (↔)

Перфектна дизюнктивна нормална форма

1. Всеки логически член на формулата съдържа всички променливи, включени във функцията F(x 1,x 2,...x n).
2. Всички логически членове на формулата са различни.
3. Нито един логически термин не съдържа променлива и нейното отрицание.
4. Нито един логически термин във формула не съдържа една и съща променлива два пъти.

Перфектен конюнктив нормална форма

1. Всички елементарни дизюнкции съдържат всички променливи, включени във функцията F(x 1 ,x 2 ,...x n).
2. Всички елементарни дизюнкции са различни.
3. Всяка елементарна дизюнкция съдържа променлива веднъж.
4. Нито една елементарна дизюнкция не съдържа променлива и нейното отрицание.