Logické operace. Disjunkce, konjunkce a negace

Logické sčítání (disjunkce) vzniká spojením dvou výroků do jednoho pomocí spojky „nebo“.

V ruštině se spojení „nebo“ používá ve dvojím smyslu.

Například, PROTI návrh Většinou ve 20 hodin koukám na televizi nebo piju čaj spojka „nebo“ je brána nevýlučně (sjednocující) smysl, protože můžeš jen koukat na televizi nebo pít jen čaj, ale můžeš i pít čaj a dívat se zároveň na televizi, protože tvoje matka není přísná. Tato operace se nazývá nepřísná disjunkce.(Kdyby byla moje matka přísná, dovolila by mi buď se dívat na televizi, nebo jen pít čaj, ale nekombinovat jídlo se sledováním televize.)

V prohlášení Toto sloveso má konjugaci I nebo II spojka "nebo"
používá výhradně (dělení) smysl. Taková operace
volal přísná disjunkce.. ,. ,-> „,... > (, r>

Příklady přísných a nepřísných disjunkcí:

Prohlášení	Typ disjunkce
Péťa sedí na západní nebo východní tribuně stadionu	Přísný
Student jede vlakem nebo čte knihu	Laxní
Olya ráda píše eseje nebo řeší logické problémy	Laxní
Seryozha studuje ve škole nebo ji absolvoval	Přísný
Zítra bude pršet nebo nebude (není žádná třetí možnost)	Přísný
Bojujme za čistotu. Čistoty je dosaženo tímto způsobem: buď nevyhazujte odpadky, nebo čistěte často	Laxní
Zelia se pohybuje po kruhové nebo eliptické dráze	Přísný
Čísla lze sčítat nebo násobit	Laxní
Děti jsou buď slušně vychované, nebo nejsou naše	?

Zápis pro slabou disjunkci:A NEBO V; ANEBOV; A| V; A PROTI V; A + B.(V tomto tutoriálu: A PROTI V.)

Uveďme příklad disjunkce dvou jednoduchých výroků.

Řekněme, že z okna vidíte parkoviště, kde jsou obvykle dvě auta: Mercedes a Zhiguli, ale může být jedno z nich nebo nemusí být žádné.

Označme výroky:

A = Na parkovišti je Mercedes. V= Na parkovišti jsou auta Zhiguli.

(A disjunkce B) = Je to na parkovišti "Mercedes" nebo "Zhiguli".

Kapitola 3. Logické operace ____________ [___________________________ SCH

Tabulka., ^"-"n..;ch; i■.■;- >i ,;,

Z pravdivostní tabulky vyplývá, že disjunkce dvou výroků je nepravdivá tehdy a jen tehdy, když jsou oba výroky nepravdivé, a pravdivá, když je alespoň jeden výrok pravdivý. Někdy je tato vlastnost brána jako definice operace disjunkce.

Mnemotechnické pravidlo: disjunkce je logické sčítání a nepochybujeme, že jste si všimli, že rovnosti 0 + 0 = 0; 0+1 = 1;1+0=1, platí pro obyčejné sčítání, platí také pro operaci disjunkce, ale 1 V 1 = 1.

Slovo „konjunkce“ má jedno písmeno „a“ a slovo „disjunkce“ má dvě písmena „a“, jako A ve slově „nebo“.

V L-Symbol V (disjunkce) je vytvořen z prvního písmene latinského slova Vel („nebo“).

"Dis" - "zaškrtnout" - V.

V teorii množin odpovídá disjunkce operaci sdružení sady.

Abychom sestrojili Euler-Vennův diagram odpovídající sjednocení množin, vybereme ty řádky pravdivostní tabulky, ve kterých AvB=\. Jsou tři. Na diagramu stínujeme tři oblasti, ve kterých jsou hodnoty AAV stejné jako ve vybraných řádcích. ^ _ h." " * "o L su J I J

30 ___________________________ Část 1. Prvky matematické logiky

Grafické znázornění: ».*■.

A V A\jB- mnoho studentů ve třídě, kteří jsou vynikajícími studenty nebo sportovci.

j Zvažte operaci přísný disjunkce (výhradní „nebo“). i Uveďme příklad striktní disjunkce.

,)■ Nechť jsou uvedena tato tvrzení:

"■ A= Na parkovišti stojí Mercedes.

>; B = Na parkovišti jsou auta Zhiguli.

IA přísná disjunkce B) = Na parkovišti stojí „Mvrsedve“*nebo

"Zhiguli". v ?;;

Použití operace „exkluzivní“ nebo „nebo“ znamená, že na parkovišti může být buď pouze Mercedes, nebo pouze Žiguli, a zakazuje situaci, kdy jsou na parkovišti Mercedes a Žiguli současně.

; . - "4",

Přísný disjunkční zápis:A XOR V; A proti V.

kapitola 3. Logické operace ______________________________________ 31

Z pravdivostní tabulky vyplývá, že operace přísné disjunkce je pravdivá tehdy a jen tehdy, když je pravdivý pouze jeden z výroků, a nepravdivá, když jsou pravdivé oba výroky nebo jsou oba nepravdivé. Někdy je tato vlastnost považována za definici operace striktní disjunkce.

Euler-Vennův diagram zobrazující striktní disjunkci je konstruován pomocí pravdivostní tabulky stejným způsobem jako pro jiné logické operace.

Grafické znázornění:

<ЗЭ

A- mnoho vynikajících studentů ve třídě; V- mnoho sportovců ve třídě;

A v B- mnoho studentů ve třídě, kteří jsou buď vynikajícími studenty, nebo sportovci.

d "TOALETA. J

Logický důsledek (implikace) -wr™

Logický důsledek (implikace) vzniká spojením dvou!,

výroky do jednoho pomocí figury řeči „jestliže..., Že ... ». ■

Příklady implikací: "

E = Pokud je složena přísaha, musí být splněna.{

P = Pokud je číslo dělitelné 9, pak je dělitelné 3. já

V logice je přípustné (přijato, odsouhlaseno) uvažovat i ne-.;:

výroky, které dávají smysl z každodenního hlediska. i

Uveďme příklady rozsudků, které jsou nejen legitimně posuzovány; oplývají logikou, ale mají také význam „pravda“:

S= Pokud krávy létají, pak 2 + 2 = 5. X = Pokud- Napoleon, pak má kočka čtyři nohy.

Označení implikace:A -> B; A=e V.(V tomto tutoriálu: A=» V.)Říkají: kdyby A,Že V; A znamená V; A znamená V; V vyplývá z A.

Část 1. Základy matematické logiky

Kapitola 3. Logické operace f; L.__________________________ 33

Tato operace není tak zřejmá jako předchozí. Dá se to vysvětlit například takto.

Nechť platí tato tvrzení: .>--.< а «<, .<-. *>,w ""Ihw

L A = Venku prší.>...;; j .„ , | G,., d

B = Asfalt je mokrý. ts

(A implikace 2?) = £bш na Venku prší, pak je asfalt mokrý.

Když pak bude pršet (A= 1) a asfalt je mokrý (5=1), pak je tento poměr
odpovídá skutečnosti, tedy pravdivé. Ale když ti to řeknou
venku prší (A= 1) a asfalt zůstane suchý (B = 0), pak počítáte
skrýváš to lžemi. Ale když venku neprší (A= 0), pak asfalt
může být suchý i vlhký (například jste právě projížděli a
hřídelový stroj). ъ. ?; t | rfl]

Stůl

Formulář výpisu: pokud A,Že V,

G SOW! ,chi , T "/1

"? , L ■ A " . "L\ a h > < "L

Lt S.Ch;":\0"1 "

Pojďme si vysvětlit konstrukci diagramu. Zajímá nás pravdivost implikace, proto vybereme ty řádky pravdivostní tabulky, ve kterých A=> V= 1. Existují tři takové řádky. Na diagramu stínujeme tři oblasti, ve kterých jsou hodnoty A A V stejně jako ve vybraných řádcích:

Z pravdivostní tabulky vyplývá, že implikace dvou tvrzení je nepravdivá právě tehdy, když nepravdivé tvrzení vyplývá z pravdivého tvrzení (když pravdivá premisa vede k nepravdivému závěru). Někdy je tato vlastnost brána jako definice operace implikace.

Podívejme se na jeden z výše uvedených příkladů důsledků, které odporují zdravému rozumu.

(A = 0) n(B = 0)

(A = 0)n (B = 1)

(L = 1)n(I = 1)

Logická rovnost (ekvivalence)

Logická rovnost (ekvivalence) vzniká spojením dvou tvrzení do jednoho pomocí obratu fráze „... tehdy a jen tehdy, když ...».

Část 1. Prvky matematické logiky^

Kapitola 3. Logické operace

Příklady ekvivalence: "

1) Úhel se nazývá vpravo a právě když on rovná se 90°.

2) Dvě čáry jsou pak rovnoběžné a jen když oni neprotínají se..,

3) Jakýkoli hmotný bod si zachovává klidový stav nebo rovnoměrný přímočarý pohyb tehdy a jen tehdy, když neexistuje žádný vnější vliv.(Newtonův první zákon.)

4) Hlava myslí tehdy a jen tehdy, když je jazyk v klidu.(Žert.)

Všechny zákony matematiky, fyziky, všechny definice jsou ekvivalence výroků.

Zápis ekvivalence: A = B; A<=>V; A ~ B.(V tomto tutoriálu: AÓ V.)

Uveďme příklad ekvivalence. Nechť jsou uvedeny následující výroky:

A= Číslo je beze zbytku dělitelné třemi (násobky tří). V= Součet číslic čísla je dělitelný 3.

(A ekvivalent B) = Číslo je dělitelné třemi právě tehdy a jen tehdy
součet jeho číslic je dělitelný 3., ;

Vysvětlení:

A	V	A<^В

Tabulka pravdy:

	Význam
	prohlášení
Význam výroků	Číslo je násobkem 3
A A V pro zadané< значений "*"	tehdy a jen kdy
*	součet jeho číslic rozdělena úplně do 3
Číslo není	Součet čísel není	Skutečný
násobek tří	násobek tří
Číslo není	Součet číslic	Lhát
násobek tří	násobek tří
Číslo je násobek	Součet čísel není	Lhát
tři	násobek tří
Číslo je násobek	Součet číslic	Skutečný
tři	násobek tří

Z pravdivostní tabulky vyplývá, že ekvivalence dvou tvrzení je pravdivá tehdy a jen tehdy, jsou-li pravdivá obě tvrzení nebo jsou obě nepravdivé. Někdy je tato vlastnost brána jako definice operace ekvivalence.

V teorii množin tato operace odpovídá operaci rovnocennost sady.

Abychom sestrojili odpovídající ekvivalenci množin v Euler-Vennově diagramu, vybereme ty řádky pravdivostní tabulky, ve kterých A<=> V= 1. Jsou dva. Na diagramu vystínujeme dvě oblasti, ve kterých jsou hodnoty AnV stejné jako ve vybraných řádcích.

Grafické znázornění: c~J_ ........ 1l...Li

Ш ZÁKLADNÍ POJMY A DEFINICE

Logická operace- způsob sestavení komplexního výroku z daných výroků, ve kterém pravdivostní hodnota komplexního výroku je zcela určena pravdivostními hodnotami původních výroků.

Inverze(logická negace) se tvoří z výroku přidáním částice „ne“ k predikátu nebo použitím figury „není pravda, že...“.

Inverzní symbol: NE A;-. A; A; NE A.>"i,t

Stůl
pravda: ■■■ g -

A	A

Inverze výroku je pravdivá, když
zobrazení je nepravdivé a nepravdivé, když prohlášení
skutečný. ■--■

! t■ .■ " N ■

Část 1. Základy matematické logiky

G Kapitola 3. Logické operace

Spojení(logické násobení) vzniká spojením dvou výroků do jednoho pomocí spojky „a“.

Konjunkční zápis: A I B; A L V; A& V; A ■ B; A A V.

; (G">* "*

Rovnocennost(logická rovnost) vzniká spojením dvou výroků do jednoho pomocí obratu fráze „...když a jen když...“.

Zápis ekvivalence: A = B; A<=> V; A ~ B.

Tabulka pravdy:

Ekvivalence dvou výroků je pravdivá tehdy a jen tehdy, když jsou oba výroky pravdivé nebo oba nepravdivé.

Disjunkce(logické sčítání) vzniká spojováním dva výroky do jednoho pomocí spojky „nebo“. ,

Disjunkční zápis: A NEBO V; A\B; L PROTI V; A+ V.

Tabulka pravdy:

Implikace(logický důsledek) vzniká spojením dva výroky do jednoho pomocí slovního obratu „když..., tak...“. Označení implikace: A->B;A=$B.

Základní shrnutí „Vlastnosti logických operací“

Tabulka pravdy:

A	V	A^B

Implikace dvou výroků je nepravdivá právě tehdy, když z pravdivého výroku vyplývá nepravdivé tvrzení.

Ch1ya" | ; - VI

. ..,... , .-. . pokud . ............... --,-

■*}■

<Ч. 1

Související informace.

Logické operace. Disjunkce, konjunkce a negace

Jak se tedy jednoduché logické výroky propojují, aby vytvořily složité? V přirozeném jazyce používáme různé spojky a další slovní druhy. Například „a“, „nebo“, „buď“, „ne“, „pokud“, „pak“, „pak“. Příklad složitých výroků: „má znalosti A dovednosti", "přijede v úterý, nebo ve středu“, „budu hrát Pak, když dělám svůj domácí úkol", "5 Ne rovná se 6". Jak rozhodneme, že to, co nám bylo řečeno, je pravda nebo ne? Nějak logicky, i někde nevědomě, na základě předchozí životní zkušenosti, chápeme, že pravda se spojením „a“ nastává v případě pravdivosti obou jednoduchých tvrzení. Jakmile se člověk stane lží, celé složité prohlášení bude nepravdivé. Ale se spojovacím výrazem „nebo“ musí být pravdivé pouze jedno jednoduché tvrzení, a pak se stane pravdivým celý výraz.

Booleovská algebra přenesla tuto životní zkušenost do aparátu matematiky, formalizovala ji a zavedla přísná pravidla pro získání jednoznačného výsledku. Odborům se zde začalo říkat logické operátory.

Algebra logiky zahrnuje mnoho logických operací. Tři z nich si však zaslouží zvláštní pozornost, protože... s jejich pomocí můžete popsat všechny ostatní, a proto při navrhování obvodů používat méně rozmanitých zařízení. Takové operace jsou spojení(A), disjunkce(NEBO) a negace(NE). Často se označuje spojka & , disjunkce - || a negace je pruh nad proměnnou označující příkaz.

U spojky vzniká pravdivost složeného výrazu pouze tehdy, jsou-li pravdivé všechny jednoduché výrazy tvořící složený výraz. Ve všech ostatních případech bude komplexní výraz nepravdivý.

S disjunkcí nastává pravdivost komplexního výrazu, když je pravdivý alespoň jeden jednoduchý výraz v něm obsažený, nebo dva najednou. Stává se, že složitý výraz se skládá z více než dvou jednoduchých. V tomto případě stačí, aby byl pravdivý jeden jednoduchý a pak bude pravdivé celé tvrzení.

Negace je unární operace, protože se provádí ve vztahu k jednomu jednoduchému výrazu nebo ve vztahu k výsledku složitého výrazu. V důsledku negace se získá nový výrok, který je opačný k původnímu.

Pravdivé tabulky

Logické operace je vhodné popisovat tzv pravdivostní tabulky, které odrážejí výsledky výpočtů složitých příkazů pro různé hodnoty původních jednoduchých příkazů. Jednoduché příkazy se označují proměnnými (například A a B).

Logické základy počítače

Počítače využívají různá zařízení, jejichž fungování dokonale popisuje algebra logiky. Mezi taková zařízení patří skupiny spínačů, spouštěčů, sčítaček.

Navíc spojení mezi Booleovou algebrou a počítači spočívá v číselném systému používaném v počítači. Jak víte, je binární. Počítačová zařízení tedy mohou ukládat a transformovat jak čísla, tak hodnoty logických proměnných.

Spínací obvody

Počítače používají elektrické obvody skládající se z mnoha spínačů. Spínač může být pouze ve dvou stavech: zavřený a otevřený. V prvním případě proud prochází, ve druhém - ne. Je velmi vhodné popsat činnost takových obvodů pomocí algebry logiky. V závislosti na poloze přepínačů můžete nebo nemusíte přijímat signály na výstupech.

Hradla, klopné obvody a sčítačky

Brána je logický prvek, který přijímá některé binární hodnoty a vytváří jiné v závislosti na jeho implementaci. Například existují hradla, která implementují logické násobení (konjunkci), sčítání (disjunkci) a negaci.

Spouštěče a sčítačky jsou poměrně složitá zařízení skládající se z jednodušších prvků – hradel.

Spoušť je schopna uložit jednu binární číslici, protože může být ve dvou stabilních stavech. Spouštěče se používají hlavně v registrech procesorů.

Sčítačky jsou široce používány v procesorových aritmetických logických jednotkách (ALU) a provádějí sčítání binárních bitů.

Konstrukce počítačů, či spíše hardwaru, je založena na tzv ventily. Jsou to poměrně jednoduché prvky, které lze vzájemně kombinovat a vytvářet tak různá schémata. Některá schémata jsou vhodná pro implementaci aritmetické operace, a na základě jiných staví různé Paměť POČÍTAČ.

Ventil je zařízení, které vytváří výsledek booleovské operace z dat (signálů), které jsou do něj vloženy.

Nejjednodušším ventilem je tranzistorový měnič, který převádí nízké napětí na vysoké napětí nebo naopak (vysoké na nízké). To si lze představit jako převod logické nuly na logickou jedničku nebo naopak. Tito. dostaneme ventil NE.

Připojením dvojice tranzistorů různými způsoby se získají hradla NEBO NE A A-NE. Tato hradla již nepřijímají jeden, ale dva nebo více vstupních signálů. Výstupní signál je vždy stejný a závisí (vytváří vysoké nebo nízké napětí) na vstupních signálech. V případě hradla NOR lze vysokého napětí (logického) dosáhnout pouze tehdy, jsou-li všechny vstupy nízké. V případě hradla NAND je tomu naopak: logickou jedničku získáme, pokud jsou všechny vstupní signály nulové. Jak vidíte, je to opak tak známých logických operací, jako je AND a OR. Obvykle se však používají hradla NAND a NOR, protože jejich implementace je jednodušší: AND-NOT a NOR-NOT jsou implementovány dvěma tranzistory, zatímco logické AND a OR jsou implementovány třemi.

Výstup hradla lze vyjádřit jako funkci vstupů.

Tranzistoru trvá velmi málo času, než se přepne z jednoho stavu do druhého (doba přepnutí se měří v nanosekundách). A to je jedna z významných výhod schémat postavených na jejich základě.

Pro logické hodnoty se běžně používají tři operace:

Spojení– logické násobení (AND) – a, &, ∧.
Disjunkce– logické sčítání (OR) – nebo, |, v.
Logická negace (NE) – ne,.

Logické výrazy lze převádět podle zákony algebry logiky:

Zákony reflexivity
a ∨ a = a
a ∧ a = a
Zákony komutativnosti
a ∨ b = b ∨ a
a ∧ b = b ∧ a
Zákony asociativnosti
(a ∧ b) ∧ c = a ∧ (b ∧ c)
(a ∨ b) ∨ c = a ∨ (b ∨ c)
Zákony distribuce
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
Zákon negace negace
(a) = a
De Morganovy zákony
(a ∧ b) = a ∨ b
(a ∨ b) = a ∧ b
Zákony absorpce
a ∨ (a ∧ b) = a
a ∧ (a ∨ b) = a

Každý logický vzorec definuje nějakou booleovskou funkci. Na druhou stranu, pro jakoukoli booleovskou funkci lze napsat nekonečně mnoho vzorců, které ji reprezentují. Jedním z hlavních úkolů logické algebry je hledání kanonicky x formy (tj. vzorce konstruované podle určitého pravidla, kánonu), stejně jako nejjednodušší vzorce reprezentující booleovské funkce.

Pokud je logická funkce vyjádřena pomocí disjunkce, konjunkce a negace proměnných, pak se tato forma zobrazení nazývá normální. Mezi normálními formami jsou takové, ve kterých jsou funkce zapsány jedinečným způsobem. Se nazývají perfektní.

Zvláštní roli v algebře logiky hrají třídy disjunktivních a konjunktivních dokonalých normálních forem. Vycházejí z pojmů elementární disjunkce a elementární konjunkce.

Vzorec se nazývá elementární konjunkce, pokud se jedná o spojení jedné nebo více proměnných, braných s negací nebo bez negace. Uvažuje se jedna proměnná nebo její negace jednočlenná elementární konjunkce.

Vzorec se nazývá elementární disjunkce, jde-li o disjunkci (třeba monomiální) proměnných a negace proměnných.

DNF A SDNF

Vzorec se nazývá disjunktivní normální forma(DNF), jde-li o disjunkci neopakujících se elementárních spojek. DNF se zapisují takto: А1 v А2 v ... v Аn, kde každý An- elementární konjunkce.

Vzorec A z k se nazývají proměnné perfektní disjunktivní normální forma(SDNF), pokud:
1.A je DNF, ve kterém je každá elementární konjunkce konjunkcí k proměnné x1, x2, …, xk, a na i-tém místě této spojky je buď proměnná xi nebo jeho popření;
2. Všechny elementární konjunkce v takovém DNF jsou párově odlišné.

Například: A = x1 & NOT x2 v x1 & x2

Dokonalá disjunktivní normální forma je formule konstruovaná podle přesně definovaných pravidel až do pořadí elementárních spojek (disjunktivních členů) v ní.

Je příkladem jedinečné reprezentace booleovské funkce ve formě formulového (algebraického) zápisu.

SDNF věta

Nechat f(x1 x2, …, xn)– Booleovská funkce n proměnné, která není shodně nulová. Pak existuje dokonalý disjunktivní normální tvar vyjadřující funkci f.

Algoritmus pro konstrukci SDNF pomocí pravdivostní tabulky:

1. V pravdivostní tabulce označíme množiny proměnných, pro které je hodnota funkce f = 1.
2.Pro každou označenou množinu zapíšeme konjunkci všech proměnných následovně: je-li hodnota některé proměnné v této množině rovna 1, zahrneme do konjunkce samotnou proměnnou, v opačném případě její negaci.
3. Všechny výsledné spojky spojíme disjunkčními operacemi.

KNF A SKNF

Vzorec se nazývá konjunktivní normální forma(CNF), jde-li o konjunkci neopakujících se elementárních disjunkcí. CNF se zapisují ve tvaru: A1 & A2 & ... & An, kde každý An– elementární disjunkce.

Vzorec A z k se nazývají proměnné dokonalá konjunktivní normální forma(SKNF), pokud:
1. A je CNF, ve kterém každá elementární disjunkce je disjunkcí k proměnné x1, x2, …, xk, a na i-tém místě této disjunkce je buď proměnná xi nebo její negace;
2. Všechny elementární disjunkce v takovém CNF jsou párově odlišné.

Například: A = (x1 v NOT x2) & (x1 v x2)

Věta SCNF

Nechat f(x1 x2, …, xn)– Booleovská funkce n proměnné, která není shodně nulová. Pak existuje dokonalá konjunktivní normální forma vyjadřující funkci f.

Algoritmus pro konstrukci SCNF pomocí pravdivostní tabulky:

1. V pravdivostní tabulce označíme množiny proměnných, pro které je hodnota funkce f = 0.
2. Pro každou označenou množinu zapíšeme disjunkci všech proměnných takto: je-li hodnota některé proměnné v této množině rovna 0, pak do disjunkce zahrneme samotnou proměnnou jinak její negaci;
3. Všechny vzniklé disjunkce spojíme konjunkčními operacemi.

Z algoritmů pro konstrukci SDNF a SCNF vyplývá, že pokud je pro většinu množin proměnných hodnot funkce rovna 0, pak je pro získání jejího vzorce snazší sestrojit SDNF, jinak - SCNF.

Minimalizace logických funkcí pomocí Karnaughových map

Karnaughova mapa je grafický způsob minimalizace přepínacích (booleovských) funkcí, poskytuje relativně snadnou práci s velkými výrazy a eliminuje potenciální rasy. Představuje operace párového neúplného lepení a elementární absorpce. Karnaughovy mapy jsou považovány za pravdivostní tabulku funkce podle toho přeuspořádané. Carnaughovy mapy lze považovat za specifický plochý vývoj n-rozměrné booleovské krychle.

Carnotovy mapy vynalezl v roce 1952 Edward W. Veitch a v roce 1953 je vylepšil Maurice Carnot, fyzik z Bellových laboratoří, a měly pomoci zjednodušit digitální elektronické obvody.

V Carnaughově mapě jsou booleovské proměnné přeneseny z pravdivostní tabulky a uspořádány pomocí Grayova kódu, ve kterém se každé další číslo liší od předchozího pouze o jednu číslici.

Hlavní metodou pro minimalizaci logických funkcí prezentovaných ve formě SDNF nebo SCNF je operace párového neúplného lepení a elementární absorpce. Operace párového lepení se provádí mezi dvěma členy (členy) obsahujícími identické proměnné, jejichž výskyty (přímé a inverzní) se shodují pro všechny proměnné kromě jedné. V tomto případě lze všechny proměnné kromě jedné vyjmout z hranatých závorek a přímé a inverzní výskyty jedné proměnné zbývající v závorkách lze slepit dohromady. Například:

Možnost absorpce vyplývá ze zřejmých rovností

Hlavním úkolem při minimalizaci SDNF a SCNF je tedy najít termíny vhodné pro lepení s následnou absorpcí, což může být u velkých tvarů docela obtížný úkol. Carnaughovy mapy poskytují vizuální způsob, jak takové výrazy najít.

Na obrázku je jednoduchá pravdivostní tabulka pro funkci dvou proměnných, 2-rozměrná krychle (čtverec) odpovídající této tabulce, dále 2-rozměrná krychle s označením členů SDNF a ekvivalentní tabulka pro seskupení členů:

Metoda Veitchova diagramu.

"Metoda umožňuje rychle získat minimální DNF booleovské funkce f malého počtu proměnných. Metoda je založena na specifikaci booleovských funkcí pomocí diagramů nějakého speciálního typu, nazývaných Veitchovy diagramy. Pro booleovskou funkci dvou proměnných je Veitchův diagram má tvar (tabulka 4.4.1).

Každá buňka v diagramu odpovídá sadě proměnných booleovské funkce v její pravdivostní tabulce. V (Tabulce 4.4.1) je tato korespondence zobrazena V buňce Veitchova diagramu je umístěna jednotka, pokud booleovská funkce přebírá hodnotu jednotky na odpovídající množině. Nulové hodnoty booleovské funkce nejsou ve Veitchově diagramu nastaveny. Pro booleovskou funkci tří proměnných má Veitchův diagram následující tvar (tabulka 4.4.2).

Přidáním stejné tabulky k ní vznikne diagram pro funkci 4 proměnných (tabulka 4.4.3).

Stejným způsobem, tedy přidáním dalšího diagramu 3 proměnných k právě uvažovanému, můžete získat diagram pro funkci 5 proměnných atd., ale diagramy pro funkce s více než 4 proměnnými se používají zřídka. Následující diagramy jsou typické:

Syntézu kombinačních obvodů lze ilustrovat řešením jednoduchého problému.

Problém 1

O osudu uchazeče rozhoduje většinou hlasů přijímací komise složená ze tří členů komise a jednoho předsedy. V případě rovného rozdělení hlasů určuje většinu skupina, ve které se nachází předseda výběrové komise. Sestavte automat, který zajistí určení většiny hlasů.

Řešení

S přihlédnutím k výše uvedeným předpokladům lze problémový stav jednoznačně znázornit ve formě pravdivostní tabulky.

Tabulku vyplníme s přihlédnutím k tomu, že funkce f je zcela definovaná, tzn. je definován na všech možných množinách proměnných x1 - x4. Pro n vstupních proměnných existuje N = 2n sad proměnných. V našem příkladu N = 24 = 16 sad.

Tyto sady mohou být zapsány v libovolném pořadí, ale lepší je to ve vzestupném pořadí binárních kódů.

Desetinná číselná soustava

Základ této číselné soustavy p je roven deseti. Tento číselný systém používá deset číslic. V současné době se k označení těchto čísel používají symboly 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Číslo v desítkové soustavě čísel se zapisuje jako součet jednotek, desítek, stovek, tisíců , a tak dále. To znamená, že váhy sousedních číslic se liší o faktor deset. Čísla menší než jedna se zapisují stejným způsobem. V tomto případě se číslice čísla budou nazývat desetiny, setiny nebo tisíciny jednotky.

Podívejme se na příklad zápisu desetinného čísla. Abychom ukázali, že příklad používá desítkovou číselnou soustavu, použijeme index 10. Pokud kromě desítkové formy zápisu čísel není zamýšleno použití jiné formy zápisu, pak se index obvykle nepoužívá:

A 10 = 247,56 10 = 2*10 2 +4*10 1 +7*10 0 +5*10 -1 +6*10 -2 = 200 10 +40 10 +7 10 +0,5 10 +0,06 10

Zde se nejvýznamnější číslice čísla bude nazývat stovky. Ve výše uvedeném příkladu stovky odpovídají číslu 2. Další číslici budeme nazývat desítky. Ve výše uvedeném příkladu číslo 4 odpovídá desítkám. Další číslici budeme nazývat jedničky. Ve výše uvedeném příkladu jednotky odpovídají číslu 7. Desetiny odpovídají číslu 5 a setiny 6.

Binární číselná soustava

Základ této číselné soustavy p je roven dvěma. Tento číselný systém používá dvě číslice. Aby nebyly vymýšleny nové symboly k označení čísel, byly v binární číselné soustavě použity symboly desetinných číslic 0 a 1 Aby nedošlo k záměně číselné soustavy při zápisu čísla, používá se index 2 kromě binární formy zápisu čísel není zamýšleno použití žádné jiné formy, pak lze tento index vynechat.

Číslo v této číselné soustavě se zapisuje jako součet jedniček, dvojek, čtyřek, osmiček a tak dále. To znamená, že váhy sousedních číslic se liší o faktor dva. Čísla menší než jedna se zapisují stejným způsobem. V tomto případě se číslice čísla budou nazývat poloviny, čtvrtiny nebo osminy jednotky.

Podívejme se na příklad zápisu binárního čísla:

A 2 = 101110,101 2 = 1*2 5 +0*2 4 +1*2 3 +1*2 2 +1*2 1 +0*2 0 +1*2 -1 +0*2 -2 + 1* 2-3 = 32 10 +8 10 +4 10 +2 10 +0,5 10 +0,125 10 =46,625 10

Při psaní příkladu desítkových ekvivalentů binárních číslic do druhého řádku jsme nepsali mocniny dvou, které se násobí nulou, protože by to vedlo pouze k zahlcení vzorce a v důsledku toho ke ztížení porozumění látce. .

Za nevýhodu binárního číselného systému lze považovat velký počet číslic potřebných k zápisu čísel. Výhodou tohoto číselného systému je snadné provádění aritmetických operací, o kterých bude řeč později.

Osmičková číselná soustava

Základ této číselné soustavy p je roven osmi. Osmičkovou číselnou soustavu lze považovat za kratší způsob zápisu binárních čísel, protože číslo osm je mocninou dvou. Tento číselný systém používá osm číslic. Aby nebyly vymýšleny nové symboly k označení čísel, byly v osmičkové číselné soustavě použity desetinné číselné symboly 0, 1, 2, 3, 4, 5, 6 a 7, aby nedošlo k záměně číselné soustavy, index 8 se používá při zápisu čísla Kromě osmičkového tvaru zápisu čísel se nepředpokládá použití jiné formy zápisu, pak lze tento index vynechat.

Číslo v této číselné soustavě se zapisuje jako součet jedniček, osmiček, šedesáti čtyřek a tak dále. To znamená, že váhy sousedních číslic se liší faktorem osm. Čísla menší než jedna se zapisují stejným způsobem. V tomto případě se číslice čísla budou nazývat osminy, šedesát čtyři atd., zlomky jedné.

Podívejme se na příklad zápisu osmičkového čísla:

A 8 =125,46 8 = 1*8 2 +2*8 1 +5*8 0 +4*8 -1 +6*8 -2 = 64 10 +16 10 +5 10 +4 10 /8 10 + 6 10 /64 10 = 85,59375 10

Druhý řádek výše uvedeného příkladu ve skutečnosti převádí číslo zapsané v osmičkovém tvaru do desítkové reprezentace stejného čísla. To znamená, že jsme se vlastně podívali na jeden ze způsobů, jak převést čísla z jedné formy reprezentace do druhé.

Vzhledem k tomu, že vzorec používá jednoduché zlomky, je možné, že přesný překlad z jedné formy reprezentace do druhé nebude možný. V tomto případě jsou omezeny na určitý počet desetinných číslic.

Typy digitálních komparátorů

Komparátor pro porovnávání signálů různé polarity

Komparátor pro porovnávání unipolárních signálů

Komparátor pro porovnávání unipolárních napětí s hysterezní charakteristikou. V uvažovaných komparátorech lze získat charakteristiky s hysterezními vlastnostmi. Zavedení hystereze do provozu komparátoru poněkud snižuje přesnost srovnání, ale činí jej imunním vůči šumu a rušení. Hystereze je dosaženo zapnutím vyššího referenčního napětí, když se napětí mění z nízké na vysokou úroveň, ve srovnání s hodnotou použitou při změně napětí z vysoké na nízkou úroveň. V tomto případě se vysoká hodnota referenčního napětí nazývá horní práh odezvy a nízká hodnota se nazývá dolní práh odezvy. Toho je dosaženo zavedením pozitivní zpětné vazby.

Vícebitové komparátory

Uvažujme jako příklad čtyřbitový digitální komparátor řady K555SP1, jehož osm vstupů slouží k propojení dvou čtyřbitových slov: A0. A3, B0. B3 k porovnání. Řídicí vstupy I(A>B), (A = B) a I(A< В) могут быть использованы для наращивания разрядности компаратора. Предусмотрены три выхода результата сравнения: А>B, A = B a A<В.

Pravdivostní tabulka takového komparátoru (Tabulka 1) je rozdělena řádek po řádku na tři části.

První část (8 horních řádků tabulky) definuje případ, kdy komparátor pracuje, když se porovnávaná čtyřbitová slova navzájem nerovnají. V tomto případě signály na vstupech zvýšení bitové hloubky jako reakce na signály nižších bitů porovnávaných slov nemají žádný vliv na výsledek porovnání.

Rýže. 1. Konvenční grafické znázornění komparátoru typu SP1

Tři řádky druhé části této tabulky charakterizují činnost komparátoru se sekvenčním způsobem zvyšování bitové hloubky, tzn. když jsou výstupy komparátoru nižšího řádu připojeny k řídicím vstupům komparátoru vyššího řádu.

Jednobitové komparátory

Jednobitový komparátor má dva vstupy, které současně přijímají jednobitová binární čísla x1 a x2, a tři výstupy (=, >,<). Из таблицы истинности логические уравнения компаратора при сравнении x1 с x2 получаются в виде

Implementace takového komparátoru na bázi NAND vede k následujícímu obrázku (obr. 2):

Obrázek 2. Jednobitový komparátor binárních čísel.

Tabulka 1. Pravdivostní tabulka čtyřbitového komparátoru typu SP1

Komparátor(analogové signály) (angl. komparátor - porovnávací zařízení) - elektronický obvod, který na svých vstupech přijímá dva analogové signály a vytváří logickou „1“, pokud je signál na přímém vstupu („+“) větší než na inverzním vstupu (“−” ), a logická “0”, pokud je signál na přímém vstupu menší než na inverzním vstupu.

Jedno srovnávací napětí binárního komparátoru rozděluje celý rozsah vstupního napětí na dva podrozsahy. Binární logický signál (bit) na výstupu binárního komparátoru udává, ve kterém ze dvou podrozsahů je vstupní napětí.

Nejjednodušším komparátorem je diferenciální zesilovač. Komparátor se liší od lineárního operačního zesilovače (op-amp) v konstrukci vstupního i výstupního stupně:

Vstupní stupeň komparátoru musí odolat širokému rozsahu vstupních napětí mezi invertujícím a neinvertujícím vstupem až do výkyvu napájecích napětí a rychle se zotavit při změně znaménka tohoto napětí.
Koncový stupeň komparátoru je kompatibilní z hlediska logických úrovní a proudů se specifickým typem vstupů logických obvodů (TTL, ESL technologie atd.). Jsou možné koncové stupně založené na jednom tranzistoru s otevřeným kolektorem (kompatibilní s logikou TTL a CMOS).
Pro vytvoření hysteretické přenosové charakteristiky jsou komparátory často pokryty pozitivní zpětnou vazbou. Toto opatření zabraňuje rychlému nechtěnému přepínání výstupního stavu v důsledku šumu ve vstupním signálu, když se vstupní signál pomalu mění.

Když je referenční srovnávací napětí přivedeno na invertující vstup, je vstupní signál přiveden na neinvertující vstup a komparátor je neinvertující (sledovač, vyrovnávací paměť).

Přivedením referenčního srovnávacího napětí na neinvertující vstup se vstupní signál přivede na invertující vstup a komparátor se invertuje (invertuje).

Poněkud méně běžně se používají komparátory založené na logických prvcích pokrytých zpětnou vazbou (viz např. Schmittova spoušť - není to komparátor ze své podstaty, ale zařízení s velmi podobným rozsahem použití).

Při matematickém modelování komparátoru nastává problém výstupního napětí komparátoru, když jsou napětí na obou vstupech komparátoru stejná. V tomto bodě je komparátor ve stavu nestabilní rovnováhy. Problém lze vyřešit mnoha různými způsoby, které jsou popsány v podkapitole „porovnávač softwaru“.

Pulzní čítač– elektronické zařízení určené k počítání počtu impulsů přivedených na vstup. Počet přijatých impulsů je vyjádřen v binární číselné soustavě.

Pulzní čítače jsou typem registrů (počítacích registrů) a jsou postaveny na klopných, respektive logických prvcích.

Hlavními ukazateli čítačů jsou čítací koeficient K 2n - počet impulsů, které může čítač spočítat. Například počítadlo sestávající ze čtyř klopných obvodů může mít maximální čítací faktor 24=16. Pro čtyřspouštěcí čítač je minimální výstupní kód 0000, maximální -1111 a při počítacím koeficientu Kc = 10 se výstupní počet zastaví na kódu 1001 = 9.

Obrázek 1, a ukazuje obvod čtyřbitového čítače používajícího T-klopné obvody zapojené v sérii. Čítací impulsy jsou přiváděny na čítací vstup prvního klopného obvodu. Čítací vstupy následujících klopných obvodů jsou propojeny s výstupy předchozích klopných obvodů.

Činnost obvodu je znázorněna časovými diagramy znázorněnými na obrázku 1b. Při příchodu prvního čítacího impulsu přejde při jeho poklesu první spoušť do stavu Q1 = 1, tzn. Digitální kód 0001 se zapíše do čítače Na konci druhého počítacího impulsu se první spoušť přepne do stavu „0“ a druhá do stavu „1“. Počítadlo zaznamená číslo 2 s kódem 0010.

Obrázek 1 – Binární čtyřbitový čítač: a) obvod, b) grafické označení, c) časová schémata činnosti

Z diagramu (obr. 1, b) je zřejmé, že např. podle poklesu 5. pulzu se do počítadla zapisuje kód 0101, podle 9. - 1001 atp. Na konci 15. pulsu se všechny bity čítače nastaví do stavu „1“ a při poklesu 16. pulsu se všechny spouštěče resetují, tj. čítač přejde do původního stavu. Pro vynulování počítadla je k dispozici vstup „reset“.

Počítací koeficient binárního čítače zjistíme ze vztahu Ксч = 2n, kde n je počet bitů (triggerů) čítače.

Počítání počtu pulzů je nejběžnější operací v zařízeních pro digitální zpracování informací.

Během činnosti binárního čítače je frekvence opakování pulzů na výstupu každého následujícího spouštěče poloviční ve srovnání s frekvencí jeho vstupních pulzů (obr. 1, b). Proto se čítače používají i jako děliče kmitočtu.

Kodér(také nazývaný kodér) převádí signál na digitální kód, nejčastěji dekadická čísla do dvojkové číselné soustavy.

Kodér má m vstupů, číslovaných postupně desetinnými čísly (0, 1,2,..., m - 1) a n výstupů. Počet vstupů a výstupů je určen závislostí 2n = m (obr. 2, a). Symbol „CD“ je tvořen písmeny v anglickém slově Coder.

Přivedení signálu na jeden ze vstupů má za následek, že se na výstupech objeví n-bitové binární číslo odpovídající číslu vstupu. Například, když je impuls přiveden na 4. vstup, objeví se na výstupech digitální kód 100 (obr. 2, a).

Dekodéry (také nazývané dekodéry) se používají k převodu binárních čísel zpět na malá desetinná čísla. Vstupy dekodéru (obr. 2, b) jsou určeny pro dodávání binárních čísel, výstupy jsou postupně číslovány desetinnými čísly. Když je na vstupy přivedeno binární číslo, objeví se na konkrétním výstupu signál, jehož číslo odpovídá číslu vstupu. Například při použití kódu 110 se signál objeví na 6. výstupu.

Obrázek 2 – a) UGO kodér, b) UGO dekodér

Multiplexer- zařízení, ve kterém je výstup připojen k jednomu ze vstupů v souladu s kódem adresy. Že. Multiplexer je elektronický spínač nebo komutátor.

Obrázek 3 – Multiplexer: a) grafické označení, b) tabulka stavů

Na vstupy A1, A2 je přiveden adresový kód, který určuje, který ze signálových vstupů bude přenášen na výstup zařízení (obr. 3).

K převodu informací z digitální do analogové formy používají digitálně-analogové převodníky (DAC) a pro inverzní transformaci - analogově-digitální převodníky (ADC).

Vstupní signál DAC je binární vícebitové číslo a výstupní signál je napětí Uout generované na základě referenčního napětí.

Postup analogově-digitální konverze (obr. 4) se skládá ze dvou fází: časové vzorkování (vzorkování) a kvantování úrovně. Proces vzorkování spočívá v měření hodnot spojitého signálu pouze v diskrétních bodech v čase.

Obrázek 4 – Proces převodu z analogového na digitální

Pro kvantování je rozsah změny vstupního signálu rozdělen na stejné intervaly - kvantizační úrovně. V našem příkladu je jich osm, ale obvykle je jich mnohem více. Kvantovací operace spočívá v určení intervalu, do kterého vzorkovaná hodnota spadá, a přiřazení digitálního kódu k výstupní hodnotě.

Registr je funkční jednotka, která kombinuje několik spouštěčů stejného typu.

Typy registrací:

1) Západkové registry– postaveno na latched triggerech (K155TM5; K155TM7), do kterých je záznam prováděn úrovní stroboskopického signálu.

Ve spoušti K155TM8 je záznam prováděn kladnou hranou stroboskopického signálu.

2) Posunové registry– vykonávat funkci pouze sekvenčního příjmu kódu.

3) Univerzální registry– může přijímat informace v paralelním a sériovém kódu.

4) Speciální registry– K589IR12 mají další možnosti použití.

Posunový registr

Jedná se o registr, jehož obsah lze po přivedení řídicího signálu posouvat směrem k vyšším nebo nižším číslicím. Například posun doleva je uveden v tabulce 9.

Tabulka 9 Posun kódu doleva

Univerzální registry

Mají externí výstupy a vstupy pro všechny bity a také sériový DS vstup.

Existují dva typy univerzálních registrů:

1) registr, který provádí posun pouze jedním směrem a přijímá kód paralelně (například K155IR1; K176IR3).

2) se čtyřmi provozními režimy: řazení vpravo/vlevo; paralelní příjem; úložiště (například 8bitový registr K155IR13; 4bitový registr K500IR141).

Hlavní elementární operací prováděnou na číselných kódech v digitálních zařízeních je aritmetické sčítání.

Logická sčítačka provozní uzel, který vykonává aritmetický sečtením kódů dvou čísel. Při aritmetickém sčítání se provádějí další dodatečné operace: zohlednění znamének čísel, zarovnání pořadí členů a podobně. Tyto operace se provádějí v aritmetických logických jednotkách (ALU) nebo procesních prvcích, jejichž jádrem jsou sčítačky.

Sčítačky jsou klasifikovány podle různých kritérií.

V závislosti na číselné soustavě rozlišovat:

binární;
binární desítkový (obecně binárně kódovaný);
desetinný;
jiné (například amplituda).

Podle počtu současně zpracovaných číslic přidaných čísel:

jedna číslice,
vícebitový.

Podle počtu vstupů a výstupů jednobitových binárních sčítaček:

čtvrťové sčítačky (prvky "součet modulo 2"; prvky "exkluzivní OR"), vyznačující se přítomností dvou vstupů, kterým jsou přiváděna dvě jednociferná čísla, a jednoho výstupu, na kterém je realizován jejich aritmetický součet;
poloviční sčítačky, charakterizované přítomností dvou vstupů, ke kterým jsou dodávány stejné číslice dvou čísel, a dvou výstupů: jeden implementuje aritmetický součet v dané číslici a druhý přenáší na další (vyšší číslici) ;
kompletní jednobitové binární sčítačky, vyznačující se přítomností tří vstupů, ke kterým jsou dodávány stejné číslice dvou čísel, které se přičítají a převod z předchozí (nižší) číslice, a dva výstupy: na jednom je aritmetický součet v tomto číslice a na druhé straně převod do dalšího (vyššího) vybití).

Způsobem reprezentace a zpracování přidaných čísel vícebitové sčítačky se dělí na:

sekvenční, ve kterém jsou čísla zpracovávána jedno po druhém, číslici po číslici na stejném zařízení;
paralelní, ve kterém se termíny sčítají současně napříč všemi číslicemi a každá číslice má své vlastní vybavení.

V nejjednodušším případě se paralelní sčítačka skládá z n jednobitových sčítaček, sekvenčně (od nejméně významného k nejvýznamnějšímu) propojených přenosovými obvody. Takový sčítací obvod se však vyznačuje relativně nízkým výkonem, protože ke generování součtových a přenosových signálů v každém i-tém bitu dochází až poté, co přenosový signál dorazí z (i-1)-tého bitu sčítačka je určena dobou šíření signálu po přenosovém řetězci. Snížení tohoto času je hlavním úkolem při konstrukci paralelních sčítaček.

Chcete-li zkrátit dobu šíření přenosového signálu, použijte: Konstruktivní rozhodnutí

VLASTNOSTI LOGICKÝCH OPERACÍ

1. Označení

1.1. Zápis pro logické spojky (operace):

A) negace(inverze, logické NOT) se značí ¬ (například ¬A);

b) spojení(logické násobení, logické AND) se značí /\
(například A/\ B) nebo & (například A & B);

C) disjunkce(logické sčítání, logické NEBO) se značí \/
(například A \/ B);

d) Následující(implikace) se označuje → (například A → B);

E) identita označované ≡ (například A ≡ B). Výraz A ≡ B je pravdivý tehdy a jen tehdy, když jsou hodnoty A a B stejné (buď jsou obě pravdivé, nebo jsou obě nepravdivé);

f) symbol 1 se používá k označení pravdy (pravdivého tvrzení); symbol 0 – pro označení lži (nepravdivého tvrzení).

1.2. Jsou volány dva booleovské výrazy obsahující proměnné ekvivalent (ekvivalent), pokud se hodnoty těchto výrazů shodují pro jakékoli hodnoty proměnných. Tedy výrazy A → B a (¬A) \/ B jsou ekvivalentní, ale A /\ B a A \/ B nikoli (význam výrazů se liší, např. když A = 1, B = 0 ).

1.3. Priority logických operací: inverze (negace), konjunkce (logické násobení), disjunkce (logické sčítání), implikace (následování), identita. ¬A \/ B \/ C \/ D tedy znamená totéž jako

((¬A) \/ B) \/ (C \/ D).

Je možné psát A \/ B \/ C místo (A \/ B) \/ C. Totéž platí pro spojku: je možné psát A /\ B /\ C místo (A /\ B ) /\ C.

2. Vlastnosti

Níže uvedený seznam NENÍ míněn jako úplný, ale doufáme, že je dostatečně reprezentativní.

2.1. Obecné vlastnosti

Za sadu n existují přesně logické proměnné 2 n různé významy. Pravdivostní tabulka pro logické vyjádření z n proměnné obsahuje n+1 sloupec a 2 n linky.

2.2.Disjunkce

Pokud alespoň jeden z podvýrazů, na které je disjunkce aplikována, platí pro nějakou sadu hodnot proměnných, pak je pro tuto sadu hodnot pravdivá celá disjunkce.
Jsou-li všechny výrazy z určitého seznamu pravdivé na určité množině hodnot proměnných, pak platí i disjunkce těchto výrazů.
Pokud jsou všechny výrazy z určitého seznamu na určité množině hodnot proměnných nepravdivé, pak je i disjunkce těchto výrazů nepravdivá.
Význam disjunkce nezávisí na pořadí zápisu podvýrazů, na které se vztahuje.

2.3. Spojení

Pokud je alespoň jeden z podvýrazů, na které je spojka aplikována, na nějaké množině hodnot proměnných nepravdivý, pak je pro tuto množinu hodnot nepravdivá celá spojka.
Pokud jsou všechny výrazy z určitého seznamu pravdivé na určité množině hodnot proměnných, pak platí i spojení těchto výrazů.
Pokud jsou všechny výrazy z určitého seznamu na určité množině hodnot proměnných nepravdivé, pak je nepravdivé také spojení těchto výrazů.
Význam spojky nezávisí na pořadí psaní podvýrazů, na které se vztahuje.

2.4. Jednoduché disjunkce a konjunkce

Nazývejme (pro pohodlí) spojku jednoduchý, jestliže podvýrazy, na které se spojka vztahuje, jsou odlišné proměnné nebo jejich negace. Podobně se nazývá disjunkce jednoduchý, jestliže podvýrazy, na které je disjunkce aplikována, jsou odlišné proměnné nebo jejich negace.

Jednoduchá konjunkce se vyhodnotí jako 1 (pravda) na přesně jedné sadě hodnot proměnných.
Jednoduchá disjunkce se vyhodnotí jako 0 (nepravda) na přesně jedné sadě hodnot proměnných.

2.5. Implikace

Implikace A →B je ekvivalentní disjunkci (¬ A) \/ B. Tato disjunkce může být také zapsána takto: ¬ A\/B.
Implikace A →B má hodnotu 0 (nepravda) pouze tehdy, když A=1 A B=0. Li A=0, pak implikace A →B pravda pro jakoukoli hodnotu B.

Spojka: odpovídá spojce: „a“, označované znaménkem^, označuje logické násobení.

Konjunkce dvou logických ~ je pravdivá tehdy a jen tehdy, když jsou pravdivé oba výroky. Lze zobecnit pro libovolný počet proměnných A^B^C = 1, pokud A=1, B=1, C=1.

Pravdivostní tabulka pro operaci „Konjunkce“:

Tabulka č. 2

Disjunkce

Logická operace odpovídá sjednocení OR, označenému znaménkem v, jinak nazývané LOGICKÉ PŘIDÁNÍ.

Disjunkce dvou logických proměnných je nepravdivá, pokud jsou nepravdivé, a oblázek je nepravdivý, pokud jsou oba výroky nepravdivé.

Tuto definici lze zobecnit na libovolný počet logických proměnných kombinovaných disjunkcí.

A v B v C = 0, pouze pokud A = O, B = O, C - 0.

Pravdivostní tabulka pro operaci „Disjunkce“:

Tabulka č. 3

Inverze

Logická operace odpovídá částici ne, označuje se ¬ nebo ¯ a je logickou negací.

Inverzní hodnota k booleovské proměnné je pravdivá, pokud je proměnná nepravda, a naopak: inverzní je nepravda, pokud je proměnná pravdivá.

Pravdivostní tabulka pro operaci "Inverze":

Tabulka č. 5

Ekvivalence „A pak B a teprve potom“ je označena A ~ B

Tabulka č. 6

Při výpočtu hodnoty logického výrazu (vzorce) se logické operace počítají v určitém pořadí podle priority:

inverze;

spojení;

disjunkce;

implikace a ekvivalence;

Operace se stejnou prioritou se provádějí zleva doprava. Závorky se používají ke změně pořadí akcí.

Formalizace prohlášení

Přirozené jazyky se používají k vytváření deskriptivních informačních modelů. V historii vědy jsou známy četné modely popisných informací; například heliocentrický model světa, který navrhl Koperník, byl formulován takto:

Země se otáčí kolem své osy a kolem Slunce;

všechny planety obíhají kolem Slunce;

Pomocí formálních jazyků se budují formální informační modely (matematické, logické atd.). Jedním z nejpoužívanějších formálních jazyků je matematika. Modely vytvořené pomocí matematických pojmů a vzorců se nazývají matematické modely. Jazyk matematiky je sbírka formálních jazyků.

Jazyk algebry umožňuje formalizovat funkční závislosti mezi veličinami. Newton tak formalizoval heliocentrický systém světa, objevil zákony mechaniky a zákon univerzální gravitace a zapsal je ve formě algebraických funkčních závislostí. Například ve školním kurzu fyziky se uvažuje o mnoha různých funkčních závislostech vyjádřených jazykem algebry, což jsou matematické modely studovaných jevů nebo procesů.

Jazyk logické algebry (výroková algebra) umožňuje vytvářet formální logické modely. Pomocí výrokové algebry můžete formalizovat (zapsat ve formě logických výrazů) jednoduché i složité výroky vyjádřené v přirozeném jazyce. Vytváření logických modelů umožňuje řešit logické problémy, sestavovat logické modely počítačových zařízení (sčítačka, spoušť) a tak dále.

Proces vytváření informačních modelů pomocí formálních jazyků se nazývá formalizace.

V procesu porozumění světu kolem nás lidstvo neustále používá modelování a formalizaci. Při studiu nového objektu je nejprve jeho popisný informační model obvykle postaven v přirozeném jazyce, poté je formalizován, to znamená vyjádřen pomocí formálních jazyků (matematika, logika atd.).

Algebra logiky a logické základy počítače

Algebra logiky (Booleova algebra) je obor matematiky, který vznikl v 19. století díky úsilí anglického matematika J. Boulya. Zpočátku neměla Booleova algebra žádný praktický význam. Jeho ustanovení však již ve 20. století našla uplatnění při popisu fungování a vývoje různých elektronických obvodů. Zákony a aparát logické algebry se začaly využívat při návrhu různých částí počítačů (paměť, procesor). Ačkoli to není jediná oblast použití této vědy.

Co je to? algebra logiky? Nejprve studuje metody pro stanovení pravdivosti nebo nepravdivosti složitých logických tvrzení pomocí algebraických metod. Za druhé, Booleova algebra to dělá tak, že komplexní logický výrok je popsán funkcí, jejíž výsledek může být buď pravdivý nebo nepravdivý (1 nebo 0). V tomto případě mohou mít argumenty funkce (jednoduché příkazy) také pouze dvě hodnoty: 0 nebo 1.

Co je jednoduché logické tvrzení? Jsou to fráze jako „dva je více než jedna“, „5,8 je celé číslo“. V prvním případě máme pravdu a ve druhém máme lež. Algebra logiky se netýká podstaty těchto tvrzení. Pokud někdo usoudí, že tvrzení „Země je čtvercová“ je pravdivé, pak to algebra logiky přijme jako fakt. Faktem je, že Booleovská algebra se zabývá výpočtem výsledku složitých logických příkazů na základě dříve známých hodnot jednoduchých příkazů.

Logické operace. Disjunkce, konjunkce a negace

Jak rozhodneme, že to, co nám bylo řečeno, je pravda nebo ne? Nějak logicky, i někde nevědomě, na základě předchozí životní zkušenosti, chápeme, že pravda se spojením „a“ nastává v případě pravdivosti obou jednoduchých tvrzení. Jakmile se člověk stane lží, celé složité prohlášení bude nepravdivé. Ale se spojovacím výrazem „nebo“ musí být pravdivé pouze jedno jednoduché tvrzení, a pak se stane pravdivým celý výraz.

Algebra logiky zahrnuje mnoho logických operací. Tři z nich si však zaslouží zvláštní pozornost, protože... s jejich pomocí můžete popsat všechny ostatní, a proto při navrhování obvodů používat méně rozmanitých zařízení. Takovými operacemi jsou konjunkce (AND), disjunkce (OR) a negace (NOT). Spojka je často označena &, disjunkce || a negace pruhem nad proměnnou označující výrok.

Na connection@/a> true with nepravdivý výraz vzniká pouze tehdy, jsou-li všechny jednoduché výrazy, které tvoří složený, pravdivé. Ve všech ostatních případech bude komplexní výraz nepravdivý.

Na disjunkce pravda komplexní výraz nastane, když alespoň jeden jednoduchý výraz v něm obsažený je pravdivý nebo dva najednou. Stává se, že složitý výraz se skládá z více než dvou jednoduchých. V tomto případě stačí, aby byl pravdivý jeden jednoduchý a pak bude pravdivé celé tvrzení.

Negace- jedná se o unární operaci, protože se provádí ve vztahu k jednomu jednoduchému výrazu nebo ve vztahu k výsledku složitého výrazu. V důsledku negace se získá nový výrok, který je opačný k původnímu.

Pro logické hodnoty se běžně používají tři operace:

Konjunkce - logické násobení (AND) - a, &, ∧.

Disjunkce - logické sčítání (OR) - nebo, |, v.

Logická negace (NOT) - ne,.

Logické operace je vhodné popisovat tzv. pravdivostními tabulkami, které odrážejí výsledky výpočtů složitých příkazů pro různé hodnoty původních jednoduchých příkazů. Jednoduché příkazy se označují proměnnými (například A a B).

Logické základy počítače

Počítače využívají různá zařízení, jejichž fungování dokonale popisuje algebra logiky. Mezi taková zařízení patří skupiny spínačů, spouštěčů, sčítaček.

Spínací obvody

Hradla, klopné obvody a sčítačky

Spouštěče A zmije- jedná se o poměrně složitá zařízení skládající se z jednodušších prvků - ventilů.

Spoušť je schopna uložit jednu binární číslici, protože může být ve dvou stabilních stavech. Spouštěče se používají hlavně v registrech procesorů.

Sčítačky jsou široce používány v procesorových aritmetických logických jednotkách (ALU) a provádějí sčítání binárních bitů.

Informace a informační procesy. Typy informací, jejich binární kódování. Množství informace, přístupy k definování pojmu „množství informace“, jednotky měření informace. Binární kódování číselných, textových, grafických, zvukových informací

Informace(z latinského informatio - „vysvětlení, prezentace, povědomí“) - informace o něčem, bez ohledu na formu jeho prezentace.

V současné době neexistuje jediná definice informace jako vědeckého pojmu. Z hlediska různých oblastí vědění je tento pojem popsán svým specifickým souborem charakteristik. Pojem „informace“ je základní v kurzu informatiky, kde je nemožné jej definovat pomocí jiných, „jednoduchších“ pojmů.

Informační vlastnosti:

Objektivita (informace je objektivní, pokud nezávisí na něčím názoru nebo úsudku);

Spolehlivost (informace jsou spolehlivé, pokud odrážejí skutečný stav věcí);

Úplnost (informace jsou úplné, pokud jsou dostatečné pro pochopení a rozhodnutí);

Relevance (informace jsou relevantní, aktuální, pokud jsou důležité, významné pro současnou dobu);

Užitečnost (hodnotí se úkoly, které s její pomocí můžeme vyřešit);

Srozumitelnost (informace je srozumitelná, pokud je vyjádřena v jazyce srozumitelném příjemci);

Dostupnost (informace jsou dostupné, pokud je můžeme získat).

Informační proces- soubor po sobě jdoucích akcí (operací) prováděných s informacemi (ve formě dat, informací, faktů, myšlenek, hypotézy, teorie atd.) k získání jakéhokoli výsledku (dosažení cíle).

Informace se projevuje právě v informačních procesech. Informační procesy vždy probíhají v nějakém systému (sociálním, sociotechnickém, biologickém atd.).

Nejobecnějšími informačními procesy jsou shromažďování, transformace a používání informací.

Mezi hlavní informační procesy studované v kurzu informatiky patří: vyhledávání, výběr, ukládání, přenos, kódování, zpracování a ochrana informací.

Informační procesy prováděné pomocí určitých informačních technologií tvoří základ informační činnosti člověka.

Počítač je univerzální zařízení pro automatizované provádění informačních procesů.

Lidé pracují s mnoha druhy informací. Komunikace lidí mezi sebou doma a ve škole, v práci i na ulici je přenos informací. Příběh učitele nebo přítele, televizní program, telegram, dopis, ústní zpráva atd. - to vše jsou příklady přenosu informací.

A už jsme o tom mluviliže stejné informace mohou být přenášeny a přijímány různými způsoby. Chcete-li tedy najít cestu do muzea v neznámém městě, můžete se zeptat kolemjdoucího, získat pomoc od informačního pultu, zkusit na to přijít sami pomocí mapy města nebo nahlédnout do průvodce. Když posloucháme výklad učitele, čteme knihy nebo noviny, sledujeme televizní zprávy, navštěvujeme muzea a výstavy – v této době přijímáme informace.

Přijaté informace si člověk ukládá do hlavy. Lidský mozek je obrovské úložiště informací. Poznámkový blok nebo sešit, váš diář, školní sešity, knihovna, muzeum, kazeta s nahrávkami vašich oblíbených melodií, videokazety – to vše jsou příklady ukládání informací.

Informace lze zpracovat: překlad textu z angličtiny do ruštiny a naopak, výpočet součtu daných výrazů, řešení problému, vybarvování obrázků nebo vrstevnic - to vše jsou příklady zpracování informací. Všichni jste někdy milovali vybarvování v omalovánkách. Ukazuje se, že v této době jste byli zapojeni do důležitého procesu - zpracování informací, přeměna černobílé kresby na barevnou.

Informace mohou být dokonce ztraceny. Dejme tomu, že Dima Ivanov zapomněl svůj deník doma, a proto si domácí úkol napsal na papír. Ale když hrál o přestávce, udělal z něj letadlo a vypustil ho. Když se Dima vrátil domů, nemohl udělat svůj domácí úkol, ztratil informace. Nyní si potřebuje buď zkusit zapamatovat, na co se ho ptali, nebo zavolat spolužákovi, aby získal potřebné informace, nebo jít do školy s nedokončeným domácím úkolem.

Binární kódování - jeden z nejběžnějších způsobů prezentace informací. V počítačích, robotech a numericky řízených strojích jsou zpravidla všechny informace, se kterými zařízení pracuje, zakódovány ve formě slov binární abecedy.

Binární abeceda se skládá ze dvou číslic 0 a 1.

Digitální počítače (osobní počítače patří do digitální třídy) používají binární kódování jakékoli informace. Vysvětluje se to především tím, že bylo technicky jednodušší postavit technické zařízení, které přesně rozlišuje mezi 2 různými stavy signálu, než zařízení, které přesně rozlišuje mezi 5 nebo 10 různými stavy.

Mezi nevýhody binárního kódování patří velmi dlouhé záznamy binárního kódu, což ztěžuje práci s nimi.