Algebra van uitspraken. Booleaanse bewerkingen

Plan

Verklaringen met externe ontkenning.

conjunctieve uitspraken.

disjunctieve uitspraken.

Strikt disjuncte uitspraken.

Uitspraken over gelijkwaardigheid.

Impliciete uitspraken.

Verklaringen met externe ontkenning.

Een uitspraak met externe ontkenning is een uitspraak (oordeel) waarin de afwezigheid van een bepaalde situatie wordt bevestigd. Het wordt meestal uitgedrukt in een zin die begint met de zin "het is niet waar dat..." of "het is verkeerd dat...". Externe negatie wordt aangegeven door het symbool "ù", het negatieteken genoemd. Dit teken wordt bepaald door de volgende waarheidstabel:

In verklaringen met externe ontkenning wordt de situatie in A ontkend, bijvoorbeeld als A: "De Wolga stroomt in de Zwarte Zee", dan ùA: "Het is niet waar dat de Wolga in de Zwarte Zee stroomt."

conjunctieve uitspraken.

Conjunctieve uitspraken zijn uitspraken waarin het gelijktijdige bestaan ​​van twee situaties wordt bevestigd. Conjunctieve uitspraken worden gevormd uit twee uitspraken met behulp van de vakbonden "en", "a", "maar". Vorm van conjunctieve uiting: (A&B). Elk van de uitspraken A en B kan zowel de waarde "true" als de waarde "false" aannemen. Deze waarden zijn kortheidshalve aangegeven met de letters ik, ik. De waarheidstabel voor conjunctieve uitspraken is als volgt:

In conjunctieve uitspraken wordt gesteld dat de situatie beschreven in A en in B gelijktijdig plaatsvindt. Voorbeelden van conjunctieve uitspraken: "De aarde is een planeet en de maan is een satelliet"; "Petrov beheerste logica goed, maar Sidorov beheerste logica slecht"; “Het is donker buiten en de lichten in de zaal branden”; "Petrov gaf de ambtenaar contant geld en Sidorov gaf hem een ​​fles."

disjunctieve uitspraken.

Disjunctieve uitspraken zijn uitspraken die het bestaan ​​bevestigen van ten minste een van de twee situaties beschreven in A en B. Een disjunctie wordt aangegeven met het symbool V en wordt in natuurlijke taal uitgedrukt door de unie "of".

De tabeldefinitie van het disjunctieteken is als volgt:

Een voorbeeld van een disjunctieve verklaring: "Roman Sergejevitsj Ivanov is een leraar, of Roman Sergejevitsj Ivanov is een afgestudeerde student."

Strikt disjunctieve verklaringen.

Strikt disjunctieve uitspraken zijn uitspraken die het bestaan ​​bevestigen van precies een van de twee situaties beschreven in A en B. Dergelijke uitspraken worden meestal uitgevoerd door middel van zinnen met de unie "of ..., of ..." ("ofwel ..., of ..."). Strikte disjunctie wordt aangegeven met het symbool V* (lees "ofwel... of...").

De tabeldefinitie van het strikte scheidingsteken is als volgt:

Een voorbeeld van een strikt disjunctieve uitspraak: "Of het is zonnig buiten, of het regent."

Waarheidswaarde

Dit artikel of gedeelte is een ruwe vertaling van een artikel in een andere taal (zie Vertalingen controleren). Het kan zijn gegenereerd door een vertaalprogramma, of gemaakt door iemand met weinig kennis van de oorspronkelijke taal. ¬( Patroon:Mvar∧Patroon:Mvar) ¬ ¬Patroon:Mvar ∨ ¬Patroon:Mvar ¬( Patroon:Mvar∨Patroon:Mvar) ¬ ¬Patroon:Mvar ∧ ¬Patroon:Mvar Meerwaardige logica Meerwaardige logica (bijvoorbeeld fuzzy logic laat meer dan twee waarheidswaarden toe, die mogelijk enkele interne structuren bevatten. Algebraïsche semantiek Niet alle logische systemen zijn echte waardesystemen in die zin dat logische connectieven kunnen worden geïnterpreteerd als de waarheid van functies. Intuïtionistische logica mist bijvoorbeeld een complete set waarheidswaarden omdat de semantiek ervan wordt gedefinieerd in termen van de bewijsbaarheid van de voorwaarde, en niet direct in termen van de verplichte geldigheid van formules. In andere theorieën Intuïtionistische typetheorie gebruikt typen in plaats van waarheidswaarden. De topos-theorie gebruikt waarheidswaarden in een speciale betekenis: de waarheidswaarde van een topos is het globale element x subobject van de classifier. Het hebben van de waarde van waarheid in deze zin heeft niet de waardelogica van waarheid. zie ook Links Wikimedia Stichting. 2010 . Kijk wat de "Waarheidswaarde" is in andere woordenboeken: Inhoud aangegeven door een of andere taalkundige uitdrukking door een woord, zin, teken, enz. De kwestie van de Z. van linguïstische uitdrukkingen wordt bestudeerd door linguïstiek, semiotiek en logische semantiek. Onderscheid onderwerp, semantisch en expressief Z. linguïstisch ... Filosofische Encyclopedie De waarde van waarheid (in logica), de waarde die de Verklaring (zin, oordeel) aanneemt, beschouwd in relatie tot de inhoud die erin wordt weergegeven. In de gewone (klassieke) logica zijn twee I. z. "waar onwaar"; in… … Grote Sovjet Encyclopedie Een waarheidstabel is een tabel die een logische functie beschrijft. Met "logische functie" wordt in dit geval een functie bedoeld waarin de waarden van de variabelen (functieparameters) en de waarde van de functie zelf de logische waarheid uitdrukken. ... ... Wikipedia Een tabel die de waarheidswaarde van een samengestelde verklaring vaststelt, gegeven de waarden van de eenvoudige verklaringen. In de klassieke wiskundige logica wordt aangenomen dat elk priemgetal (zonder logische ... ... Woordenlijst van logische termen Denotatum (van het Latijnse denotatum, aangeduid), een term uit de taalkunde en extensionele logica, die 1) extensie, 2) designatum, 3) referent en 4) semantische kern van betekenis aanduidt. Inhoud 1 Denotatie als extensie 2 Denotatie als aanduiding ... Wikipedia Een van de mogelijke kenmerken van de uitspraak in termen van overeenstemming met het beschreven fragment van de werkelijkheid. Als wordt aangenomen dat elke bewering waar of onwaar is (d.w.z. dat het waar is ... Woordenlijst van logische termen Een reeks logische systemen gebaseerd op het ambiguïteitsprincipe. In de klassieke tweewaardige logica nemen uitdrukkingen tijdens de interpretatie slechts twee waarden "true" en "false" aan, in M.l. er wordt bijvoorbeeld ook gekeken naar andere waarden. "voor onbepaalde tijd" ... ... Filosofische Encyclopedie - (van lat. factum gedaan, volbracht) 1) een synoniem voor de begrippen "waarheid", "gebeurtenis", "resultaat"; iets echts in tegenstelling tot fictief; concreet, enkelvoud in tegenstelling tot het abstracte en algemene; 2) in de wetenschapsfilosofie van een speciaal soort p ... Filosofische Encyclopedie - (in logistiek) - de waarheid van de zin (oordeel, verklaring), vanwege, in tegenstelling tot de zogenaamde. logisch waarheid, de inhoud van deze zin. Met andere woorden, een zin is echt waar als de waarheid ervan afhangt van de waarden... Filosofische Encyclopedie Stereometrische semantiek- de interpretatie van logica als de wetenschap van het verkrijgen van ware consequenties uit ware premissen maakt in toenemende mate plaats voor een breder concept dat ofwel verband houdt met een veralgemening van het concept van volgen, gebaseerd op traditionele waarheidsbeoordeling en op praktische ... ... Projectief Filosofisch Woordenboek Boeken Hoe oprecht te geloven in God, of het enige dat telt voor de ontwikkeling van het geloof, Vrajev V. omgeving met...

propositielogica , ook wel propositielogica genoemd - een tak van wiskunde en logica die de logische vormen van complexe uitspraken bestudeert die zijn opgebouwd uit eenvoudige of elementaire uitspraken met behulp van logische bewerkingen.

De logica van proposities wordt geabstraheerd van de betekenisvolle lading proposities en bestudeert hun waarheidswaarde, dat wil zeggen of de propositie waar of onwaar is.

De afbeelding hierboven is een illustratie van een fenomeen dat bekend staat als de leugenaarsparadox. Tegelijkertijd zijn dergelijke paradoxen volgens de auteur van het project alleen mogelijk in omgevingen die niet vrij zijn van politieke problemen, waar iemand a priori voor leugenaar kan worden gebrandmerkt. In de natuurlijke gelaagde wereld op het onderwerp "waarheid" of "onwaarheid" wordt alleen beoordeeld als afzonderlijk genomen uitspraken . En later in deze les maak je kennis met: de mogelijkheid om veel uitspraken over dit onderwerp te evalueren (en kijk dan naar de juiste antwoorden). Inclusief complexe uitspraken waarin eenvoudigere met elkaar zijn verbonden door tekens van logische bewerkingen. Maar laten we eerst eens kijken naar deze bewerkingen op proposities zelf.

Propositionele logica wordt gebruikt in de informatica en programmering in de vorm van het declareren van logische variabelen en het toewijzen van de logische waarden "false" of "true", waarvan het verloop van de verdere uitvoering van het programma afhangt. In kleine programma's waar slechts één booleaanse variabele bij betrokken is, krijgt die booleaanse variabele vaak een naam, zoals "flag" en de "flag" wordt geïmpliceerd wanneer de waarde van die variabele "true" is en "flag is down" wanneer de waarde van deze variabele is "false". In grote programma's, waarin er meerdere of zelfs veel logische variabelen zijn, moeten professionals namen van logische variabelen bedenken die de vorm hebben van statements en een semantische belasting die ze onderscheidt van andere logische variabelen en begrijpelijk is voor anderen. professionals die de tekst van dit programma zullen lezen.

Er kan dus een logische variabele met de naam "UserRegistered" (of het Engelse equivalent daarvan) worden gedeclareerd, in de vorm van een instructie, waaraan de logische waarde "true" kan worden toegekend als aan de voorwaarden is voldaan dat de gegevens voor registratie worden verzonden door de gebruiker en deze gegevens worden door het programma als geldig herkend. Bij verdere berekeningen kunnen de waarden van de variabelen veranderen afhankelijk van welke logische waarde ("true" of "false") de variabele "UserLogged in" heeft. In andere gevallen kan een variabele, bijvoorbeeld met de naam "Meer dan drie dagen tot dag", tot een bepaald rekenblok de waarde "True" krijgen en tijdens de verdere uitvoering van het programma kan deze waarde worden opgeslagen of gewijzigd in "false" en het verloop van de verdere uitvoering hangt af van de waarde van deze variabele programma's.

Als een programma meerdere logische variabelen gebruikt waarvan de namen de vorm van proposities hebben, en er worden complexere proposities van gemaakt, dan is het veel gemakkelijker om een ​​programma te ontwikkelen als, alvorens het te ontwikkelen, alle bewerkingen van proposities worden geschreven in de vorm van formules gebruikt in de propositielogica dan we in de loop van deze les doen, en laten we het doen.

Logische bewerkingen op statements

Voor wiskundige uitspraken kan men altijd kiezen tussen twee verschillende alternatieven "waar" en "onwaar", maar voor uitspraken in "verbale" taal zijn de begrippen "waar" en "onwaar" wat vager. Echter, bijvoorbeeld verbale vormen als "Ga naar huis" en "Is het regent?" zijn geen uitingen. Daarom is het duidelijk dat uitingen zijn verbale vormen waarin iets wordt gezegd . Vragende of uitroepende zinnen, beroepen, maar ook wensen of eisen zijn geen uitspraken. Ze kunnen niet worden geëvalueerd door de waarden "true" en "false".

Stellingen daarentegen kunnen worden gezien als een grootheid die twee waarden kan aannemen: "waar" en "onwaar".

Zo worden er oordelen gegeven: "een hond is een dier", "Parijs is de hoofdstad van Italië", "3

De eerste van deze uitspraken kan worden geëvalueerd met het symbool "true", de tweede - "false", de derde - "true" en de vierde - "false". Een dergelijke interpretatie van proposities is het onderwerp van propositiealgebra. We zullen uitspraken met Latijnse hoofdletters aanduiden EEN, B, ..., en hun waarden, dat wil zeggen respectievelijk waar en onwaar En en L. In gewone spraak worden verbindingen gebruikt tussen de uitspraken "en", "of" en andere.

Deze verbindingen maken het mogelijk om, door verschillende uitspraken te combineren, nieuwe uitspraken te vormen - complexe uitspraken . Bijvoorbeeld een hoop "en". Laat de uitspraken worden gegeven: π groter dan 3" en de verklaring " π minder dan 4. U kunt een nieuwe - complexe verklaring organiseren " π meer dan 3 en π minder dan 4". De verklaring "if π irrationeel, dus π ² is ook irrationeel" wordt verkregen door twee uitspraken te koppelen met de link "als - dan". Ten slotte kunnen we een nieuwe - complexe verklaring - krijgen van elke verklaring - die de oorspronkelijke verklaring negeert.

Proposities beschouwen als hoeveelheden die de waarden aannemen En en L, definiëren we verder logische bewerkingen op statements , waarmee we nieuwe complexe uitspraken uit deze uitspraken kunnen halen.

Laat twee willekeurige uitspraken worden gegeven EEN en B.

1 . De eerste logische bewerking op deze uitspraken - conjunctie - is de vorming van een nieuwe instructie, die we zullen aanduiden EEN ∧ B en wat waar is als en slechts als EEN en B WAAR. In gewone spraak komt deze bewerking overeen met de verbinding van uitspraken met een aantal "en".

Waarheidstabel voor conjunctie:

EEN	B	EEN ∧ B
En	En	En
En	L	L
L	En	L
L	L	L

2 . De tweede logische bewerking op statements EEN en B- disjunctie uitgedrukt als EEN ∨ B, wordt als volgt gedefinieerd: het is waar als en slechts als ten minste één van de oorspronkelijke beweringen waar is. In gewone spraak komt deze bewerking overeen met de verbinding van uitspraken met een aantal "of". Hier hebben we echter een niet-scheidende "of", die wordt opgevat in de zin van "of-of" wanneer EEN en B beide kunnen niet waar zijn. In de definitie van propositielogica EEN ∨ B waar als slechts één van de beweringen waar is, en als beide beweringen waar zijn EEN en B.

Waarheidstabel voor disjunctie:

EEN	B	EEN ∨ B
En	En	En
En	L	En
L	En	En
L	L	L

3 . De derde logische bewerking op statements EEN en B, uitgedrukt als EEN → B; de resulterende verklaring is onwaar als en slechts als EEN waar, en B vals. EEN genaamd perceel , B - gevolg , en de verklaring EEN → B - in aansluiting op , ook wel een implicatie genoemd. In gewone spraak komt deze bewerking overeen met de link "if - then": "if EEN, dan B". Maar in de definitie van propositielogica is deze propositie altijd waar, ongeacht of de propositie waar of onwaar is B. Deze omstandigheid kan in het kort als volgt worden geformuleerd: "alles wat je wilt, volgt uit het valse." Op zijn beurt, als EEN waar, en B niet waar, dan de hele verklaring EEN → B vals. Het zal waar zijn als en slechts als EEN, en B WAAR. Kort samengevat kan dit als volgt worden geformuleerd: 'valse kan niet uit het ware volgen'.

Waarheidstabel om te volgen (implicatie):

EEN	B	EEN → B
En	En	En
En	L	L
L	En	En
L	L	En

4 . De vierde logische bewerking op uitspraken, meer bepaald op één uitspraak, wordt de ontkenning van een uitspraak genoemd. EEN en aangeduid met ~ EEN(u kunt ook het gebruik vinden van niet het symbool ~, maar het symbool ¬, evenals de bovenlijn over EEN). ~ EEN er is een verklaring die onwaar is wanneer EEN waar, en waar wanneer EEN vals.

Waarheidstabel voor ontkenning:

EEN	~ EEN
L	En
En	L

5 . En ten slotte, de vijfde logische bewerking op proposities wordt equivalentie genoemd en wordt aangeduid met EEN ↔ B. De resulterende verklaring EEN ↔ B is een ware uitspraak als en slechts als EEN en B beide waar of beide onwaar.

Waarheidstabel voor gelijkwaardigheid:

EEN	B	EEN → B	B → EEN	EEN ↔ B
En	En	En	En	En
En	L	L	En	L
L	En	En	L	L
L	L	En	En	En

De meeste programmeertalen hebben speciale symbolen voor logische waarden van proposities, ze worden in bijna alle talen geschreven als true (true) en false (false).

Laten we het bovenstaande samenvatten. propositielogica bestudeert verbanden die volledig worden bepaald door de manier waarop sommige uitspraken zijn opgebouwd uit andere, de zogenaamde elementaire. Elementaire uitspraken worden als geheel beschouwd, niet ontleedbaar in delen.

We systematiseren in de onderstaande tabel de namen, aanduidingen en betekenis van logische bewerkingen op uitspraken (we hebben ze binnenkort weer nodig om voorbeelden op te lossen).

Bundel	Aanwijzing	Operatie naam:
niet		negatie
en		voegwoord
of		disjunctie
als dan...		implicatie
dan en alleen dan		gelijkwaardigheid

Want logische bewerkingen zijn waar wetten van de algebra van de logica, die kan worden gebruikt om booleaanse uitdrukkingen te vereenvoudigen. Tegelijkertijd moet worden opgemerkt dat ze in de logica van proposities worden geabstraheerd van de semantische inhoud van de propositie en beperkt zijn tot het beschouwen vanuit de positie dat ze waar of onwaar is.

voorbeeld 1

1) (2 = 2) EN (7 = 7);

2) Niet (15;

3) ("Dennen" = "Eik") OF ("Kers" = "Esdoorn");

4) Niet("grenen" = "eik");

5) (Niet (15 20) ;

6) ("Ogen worden gegeven om te zien") en ("Onder de derde verdieping is de tweede verdieping");

7) (6/2 = 3) OF (7*5 = 20) .

1) De waarde van de uitspraak tussen de eerste haakjes is "true", de waarde van de uitdrukking tussen de tweede haakjes is ook waar. Beide statements zijn verbonden door de logische operatie "AND" (zie de regels voor deze operatie hierboven), dus de logische waarde van deze hele instructie is "true".

2) De betekenis van de verklaring tussen haakjes is "false". Deze instructie wordt voorafgegaan door een logische ontkenningsoperatie, dus de logische waarde van deze hele instructie is "true".

3) De betekenis van de bewering tussen de eerste haakjes is "false", de betekenis van de bewering tussen de tweede haakjes is ook "false". De statements zijn verbonden door de logische operatie "OF" en geen van de statements heeft de waarde "true". Daarom is de logische betekenis van deze hele verklaring "onwaar".

4) De betekenis van de verklaring tussen haakjes is "false". Deze verklaring wordt voorafgegaan door een logische ontkenningsbewerking. Daarom is de logische betekenis van de hele gegeven verklaring "waar".

5) In de eerste haakjes wordt de verklaring tussen de binnenste haakjes genegeerd. Deze verklaring tussen haakjes wordt geëvalueerd als "false", dus de ontkenning ervan wordt geëvalueerd tot de logische waarde "true". De verklaring tussen de tweede haakjes heeft de waarde "false". Deze twee verklaringen zijn verbonden door de logische bewerking "AND", dat wil zeggen, "true AND false" wordt verkregen. Daarom is de logische betekenis van de hele gegeven verklaring "false".

6) De betekenis van de stelling tussen de eerste haakjes is "waar", de betekenis van de stelling tussen de tweede haakjes is ook "waar". Deze twee uitspraken zijn verbonden door de logische bewerking "EN", dat wil zeggen, "waar EN waarheid" wordt verkregen. Daarom is de logische betekenis van de hele gegeven verklaring "waar".

7) De betekenis van de uitspraak tussen de eerste haakjes is "waar". De betekenis van de verklaring tussen de tweede haakjes is "onwaar". Deze twee statements zijn verbonden door de logische operatie "OF", dat wil zeggen, "true OR false" wordt verkregen. Daarom is de logische betekenis van de hele gegeven verklaring "waar".

Voorbeeld 2 Noteer de volgende complexe uitspraken met behulp van logische bewerkingen:

1) "Gebruiker niet geregistreerd";

2) "Vandaag is het zondag en sommige werknemers zijn aan het werk";

3) "De gebruiker wordt geregistreerd wanneer en alleen wanneer de door de gebruiker verzonden gegevens geldig blijken te zijn."

1) p- enkele instructie "Gebruiker is geregistreerd", logische bewerking: ;

2) p- enkele verklaring "Vandaag is het zondag", q- "Sommige medewerkers zijn aan het werk", logische bewerking: ;

3) p- enkele verklaring "Gebruiker is geregistreerd", q- "Gegevens verzonden door de gebruiker zijn geldig", logische bewerking: .

Los propositielogica-voorbeelden zelf op en kijk vervolgens naar de oplossingen

Voorbeeld 3 Bereken de booleaanse waarden van de volgende uitspraken:

1) ("Er zitten 70 seconden in een minuut") OF ("Een lopende klok geeft de tijd aan");

2) (28 > 7) EN (300/5 = 60);

3) ("TV - elektrisch apparaat") en ("Glas - hout");

4) Niet ((300 > 100) OF ("Dorst kan worden geblust met water"));

5) (75 < 81) → (88 = 88) .

Voorbeeld 4 Noteer de volgende complexe uitspraken met behulp van logische bewerkingen en bereken hun logische waarden:

1) "Als de klok de tijd niet correct aangeeft, kun je op het verkeerde moment naar de les komen";

2) "In de spiegel zie je je spiegelbeeld en Parijs - de hoofdstad van de VS";

Voorbeeld 5 Booleaanse expressie bepalen

(p → q) ↔ (r → s) ,

p = "278 > 5" ,

q= "Appel = Sinaasappel",

p = "0 = 9" ,

s= "De hoed bedekt het hoofd".

Propositionele logische formules

Het concept van de logische vorm van een complexe instructie wordt gespecificeerd met behulp van het concept propositielogica formules .

In voorbeelden 1 en 2 hebben we geleerd hoe we complexe uitspraken kunnen schrijven met behulp van logische bewerkingen. In feite worden ze propositielogische formules genoemd.

Om uitspraken aan te duiden, zoals in het bovenstaande voorbeeld, zullen we de letters blijven gebruiken

p, q, r, ..., p 1 , q 1 , r 1 , ...

Deze letters zullen de rol spelen van variabelen die de waarheidswaarden "true" en "false" als waarden aannemen. Deze variabelen worden ook wel propositievariabelen genoemd. We noemen ze voortaan elementaire formules of atomen .

Om propositielogica-formules te construeren, worden naast de bovenstaande letters de tekens van logische bewerkingen gebruikt

~, ∧, ∨, →, ↔,

evenals symbolen die de mogelijkheid bieden om formules ondubbelzinnig te lezen - haakjes links en rechts.

concept propositielogica formules definieer als volgt:

1) elementaire formules (atomen) zijn formules van propositielogica;

2) als EEN en B- propositielogica formules, dan ~ EEN , (EEN ∧ B) , (EEN ∨ B) , (EEN → B) , (EEN ↔ B) zijn ook formules van propositielogica;

3) alleen die uitdrukkingen zijn propositielogische formules waarvoor dit volgt uit 1) en 2).

De definitie van een propositielogische formule bevat een opsomming van de regels voor de vorming van deze formules. Volgens de definitie is elke formule van de propositielogica ofwel een atoom ofwel wordt ze gevormd uit atomen als resultaat van de opeenvolgende toepassing van regel 2).

Voorbeeld 6 laten zijn p- enkele verklaring (atoom) "Alle rationale getallen zijn reëel", q- "Sommige reële getallen zijn rationale getallen", r- "sommige rationale getallen zijn reëel". Vertaal in de vorm van verbale proposities de volgende formules van propositielogica:

6) .

1) "er zijn geen reële getallen die rationeel zijn";

2) "als niet alle rationale getallen echt zijn, dan zijn er geen rationale getallen die echt zijn";

3) "als alle rationale getallen reëel zijn, dan zijn sommige reële getallen rationale getallen en sommige rationale getallen zijn reëel";

4) "alle reële getallen zijn rationale getallen en sommige reële getallen zijn rationale getallen en sommige rationale getallen zijn reële getallen";

5) "alle rationale getallen zijn reëel dan en slechts dan als het niet zo is dat niet alle rationale getallen reëel zijn";

6) "het is niet zo dat het niet zo is dat niet alle rationale getallen echt zijn en er geen reële getallen zijn die rationeel zijn of geen rationale getallen die echt zijn."

Voorbeeld 7 Maak een waarheidstabel voor de propositielogica-formule , die in de tabel kan worden aangegeven f .

Beslissing. We beginnen met het samenstellen van de waarheidstabel door de waarden ("true" of "false") op te nemen voor enkele uitspraken (atomen) p , q en r. Alle mogelijke waarden worden in acht rijen van de tabel geschreven. Verder, wanneer u de waarden van de implicatiebewerking bepaalt en naar rechts in de tabel gaat, onthoud dan dat de waarde gelijk is aan "false" wanneer "true" "false" betekent.

p	q	r					f
En	En	En	En	En	En	En	En
En	En	L	En	En	En	L	En
En	L	En	En	L	L	L	L
En	L	L	En	L	L	En	En
L	En	En	L	En	L	En	En
L	En	L	L	En	L	En	L
L	L	En	En	En	En	En	En
L	L	L	En	En	En	L	En

Merk op dat geen enkel atoom de vorm ~ . heeft EEN , (EEN ∧ B) , (EEN ∨ B) , (EEN → B) , (EEN ↔ B). Dit zijn complexe formules.

Het aantal haakjes in propositielogica-formules kan worden verminderd door aan te nemen dat:

1) in een complexe formule laten we het buitenste paar haakjes weg;

2) bestel de tekens van logische bewerkingen "op anciënniteit":

↔, →, ∨, ∧, ~ .

In deze lijst heeft het ↔-teken het grootste bereik en het ~-teken het kleinste bereik. Onder de reikwijdte van een bewerkingsteken wordt verstaan ​​die delen van de propositielogica-formule waarop het weloverwogen voorkomen van dit teken wordt toegepast (waarop het inwerkt). Het is dus mogelijk om in elke formule die paren haakjes weg te laten die kunnen worden hersteld, rekening houdend met de "volgorde". En bij het terugzetten van haakjes worden eerst alle haakjes geplaatst die verwijzen naar alle exemplaren van het ~-teken (in dit geval gaan we van links naar rechts), dan naar alle exemplaren van het ∧-teken, enzovoort.

Voorbeeld 8 Herstel haakjes in de propositielogica-formule B ↔ ~ C ∨ D ∧ EEN .

Beslissing. De beugels worden stap voor stap als volgt hersteld:

B ↔ (~ C) ∨ D ∧ EEN

B ↔ (~ C) ∨ (D ∧ EEN)

B ↔ ((~ C) ∨ (D ∧ EEN))

(B ↔ ((~ C) ∨ (D ∧ EEN)))

Niet elke propositielogica-formule kan zonder haakjes worden geschreven. Bijvoorbeeld in formules MAAR → (B → C) en ~( EEN → B) geen verdere verwijdering van haakjes mogelijk.

Tautologieën en tegenstrijdigheden

Logische tautologieën (of gewoon tautologieën) zijn zulke formules van propositielogica dat als letters willekeurig worden vervangen door proposities (waar of onwaar), het resultaat altijd een ware propositie zal zijn.

Aangezien de waarheid of onwaarheid van complexe uitspraken alleen afhangt van de betekenissen, en niet van de inhoud van uitspraken, die elk overeenkomen met een bepaalde letter, kan de test of een bepaalde uitspraak een tautologie is, op de volgende manier worden vervangen. In de expressie die wordt bestudeerd, worden de waarden 1 en 0 (respectievelijk "true" en "false") op alle mogelijke manieren vervangen door de letters en met behulp van logische bewerkingen worden de logische waarden van de expressies berekend. Als al deze waarden gelijk zijn aan 1, dan is de bestudeerde uitdrukking een tautologie, en als ten minste één substitutie 0 geeft, dan is dit geen tautologie.

Dus een propositielogica-formule die de waarde "waar" aanneemt voor elke verdeling van de waarden van de atomen die in deze formule zijn opgenomen, wordt genoemd identiek ware formule of tautologie .

De tegenovergestelde betekenis is een logische tegenstrijdigheid. Als alle propositiewaarden 0 zijn, dan is de uitdrukking een logische contradictie.

Dus een propositielogica-formule die de waarde "false" neemt voor elke verdeling van de waarden van de atomen die in deze formule zijn opgenomen, wordt genoemd identiek valse formule of tegenstrijdigheid .

Naast tautologieën en logische tegenstellingen, zijn er formules van propositielogica die noch tautologieën noch contradicties zijn.

Voorbeeld 9 Maak een waarheidstabel voor een propositielogica-formule en bepaal of het een tautologie, een contradictie of geen van beide is.

Beslissing. We maken een waarheidstabel:

En	En	En	En	En
En	L	L	L	En
L	En	L	En	En
L	L	L	L	En

In de betekenis van de implicatie komen we geen regel tegen waarin "waar" "onwaar" betekent. Alle waarden van de originele verklaring zijn gelijk aan "true". Daarom is deze propositielogica-formule een tautologie.

Programma thema: Verklaringen en bewerkingen daarop.

Lesdoelen:

1) Vat theoretische kennis over het onderwerp samen: "Statements en bewerkingen daarop."

2) Overweeg algoritmen voor het oplossen van taken over het onderwerp "Statements en bewerkingen daarop", los problemen op.

3) Het vermogen vormen om de eigen activiteit te voorspellen, het vermogen om zijn activiteit te organiseren en te analyseren.

Doorlooptijd: 1 uur.

Theoretische basis

Het basisconcept van wiskundige logica is het concept van "eenvoudige verklaring". Een uitspraak wordt meestal opgevat als elke declaratieve zin die iets over iets beweert, en tegelijkertijd kunnen we zeggen of het waar of onwaar is in bepaalde omstandigheden van plaats en tijd. De logische waarden van uitspraken zijn "true" en "false".

Expressie voorbeelden.
1) Moskou staat aan de Neva.
2) Londen is de hoofdstad van Engeland.
3) De valk is geen vis.
4) Het getal 6 is deelbaar door 2 en 3.
Beweringen 2), 3), 4) zijn waar, en stelling 1) is onwaar.
Het is duidelijk dat de zin "Lang leve Rusland!" is geen verklaring.
Er zijn twee soorten verklaringen.
Een verklaring, die een enkele verklaring is, wordt meestal eenvoudig of elementair genoemd. Voorbeelden van elementaire proposities zijn proposities 1) en 2).
Uitspraken die zijn verkregen uit elementaire met behulp van grammaticale verbindingswoorden "niet", "en", "of", "als .... dan ...", "dan en alleen dan", worden gewoonlijk complex of samengesteld genoemd .
Dus de uitspraak 3) wordt verkregen uit de eenvoudige uitspraak "De Valk is een vis" met behulp van de ontkenning van "niet", de uitspraak 4) wordt gevormd uit de elementaire uitspraken "Het getal 6 is deelbaar door 2", "Het getal 6 is deelbaar door 3", verbonden door de unie "en".
Evenzo kunnen complexe uitspraken worden verkregen uit eenvoudige uitspraken met behulp van de grammaticale verbindingswoorden "of", "als en alleen dan".
In de algebra van de logica worden alle uitspraken alleen bekeken vanuit het oogpunt van hun logische betekenis, en wordt hun alledaagse inhoud geabstraheerd. Er wordt aangenomen dat elke propositie waar of onwaar is, en geen enkele propositie kan tegelijkertijd waar en onwaar zijn.
Elementaire uitspraken worden aangegeven met kleine letters van het Latijnse alfabet: x, y, z, ..., a, b, c, ...; de ware waarde van de verklaring is het cijfer 1, en de valse waarde is de letter 0.
Als de verklaring a waar, we zullen schrijven een = 1, en als a vals, dan een = 0.

Logische bewerkingen op statements

Negatie.

De ontkenning van de uitspraak x wordt een nieuwe propositie genoemd, wat waar is als de propositie X onwaar, en onwaar als de verklaring X WAAR.

Ontkenning van een verklaring X gemarkeerd en gelezen "niet X" of "het is niet waar dat x".

De logische betekenis van een uiting kan worden beschreven met behulp van een tabel.

Dergelijke tabellen worden waarheidstabellen genoemd.
laten zijn X uitspraak. Omdat het ook een verklaring is, is het mogelijk om de ontkenning van de verklaring te vormen, dat wil zeggen de verklaring, die de dubbele ontkenning van de verklaring wordt genoemd X. Het is duidelijk dat de logische betekenissen van uitspraken X en overeenkomen.

Bijvoorbeeld, voor de verklaring "Poetin is de president van Rusland", zou het negatieve de verklaring zijn "Poetin is niet de president van Rusland", en de dubbele ontkenning zou de verklaring zijn "Het is niet waar dat Poetin niet de president is van Rusland".

Voegwoord.

De conjunctie (logische vermenigvuldiging) van twee uitspraken x en y een nieuwe propositie wordt genoemd, die als waar wordt beschouwd als beide proposities x en y waar, en onwaar als ten minste één van hen onwaar is.
combinatie van proposities x en y aangegeven door het symbool x&y ( , xy), lezen "x en y". gezegden x en y worden leden van het voegwoord genoemd.
De logische waarden van de conjunctie worden beschreven door de volgende waarheidstabel:

Bijvoorbeeld, voor de uitspraken "6 is deelbaar door 2", "6 is deelbaar door 3", zal hun conjunctie de uitspraak "6 is deelbaar door 2 en 6 is deelbaar door 3" zijn, wat duidelijk waar is.

Uit de definitie van de conjunctiebewerking blijkt dat de vereniging "en" in de algebra van de logica in dezelfde betekenis wordt gebruikt als in de dagelijkse spraak. Maar in gewone spraak is het niet gebruikelijk om twee uitspraken te combineren die qua inhoud ver van elkaar verwijderd zijn met de unie "en", en in de algebra van de logica wordt de combinatie van twee willekeurige uitspraken overwogen.

disjunctie

Disjunctie (logische toevoeging) van twee uitspraken x en y er wordt een nieuwe propositie genoemd die als waar wordt beschouwd als ten minste één van de proposities x, ja waar en onwaar als beide onwaar zijn. Disjunctie van proposities x, ja aangegeven door het symbool "x v y", lezen "x of y". gezegden x, ja worden termen van de disjunctie genoemd.
De logische waarden van de disjunctie worden beschreven door de volgende waarheidstabel:

In het alledaagse spraakgebruik wordt de unie "of" in een andere betekenis gebruikt: exclusief en niet-exclusief. In de algebra van de logica wordt de unie "of" altijd in een niet-exclusieve betekenis gebruikt.

implicatie.

Implicatie van twee uitspraken x en y Er wordt een nieuwe propositie genoemd die als onwaar wordt beschouwd als x waar is en y onwaar, en in alle andere gevallen waar.
Implicatie van uitspraken x, ja aangegeven door het symbool , lezen "als x, dan y" of "uit x volgt y". uitspraak X een voorwaarde of een premisse, een verklaring genoemd Bij- gevolg of conclusie, uitspraak volgen of impliceren.

De logische waarden van de implicatiebewerking worden beschreven door de volgende waarheidstabel:

Het gebruik van de woorden "als....dan..." in de algebra van de logica verschilt van hun gebruik in de dagelijkse spraak, waar we geneigd zijn te denken dat als de uitspraak X onwaar, dan de verklaring "Als x, dan y" heeft helemaal geen zin. Bovendien, het construeren van een zin van de vorm "als x dan y" in alledaagse spraak bedoelen we altijd dat de zin Bij komt voort uit het voorstel X. Het gebruik van de woorden "als ... dan ..." in de wiskundige logica vereist dit niet, omdat de betekenis van uitspraken daarin niet wordt beschouwd.
Implicatie speelt een belangrijke rol bij wiskundige bewijzen, aangezien veel stellingen in voorwaardelijke vorm zijn geformuleerd. "Als x, dan y." Als echter bekend is dat X is waar en de waarheid van de implicatie is bewezen , dan kunnen we concluderen dat de conclusie waar is Bij .

Gelijkwaardigheid.

Gelijkwaardigheid van twee uitspraken x en y een nieuwe propositie wordt genoemd, die als waar wordt beschouwd wanneer beide proposities x, ja ofwel beide waar of beide onwaar, en onwaar in alle andere gevallen.

Verklaring gelijkwaardigheid x, ja aangegeven met het symbool, lees "voor x is het noodzakelijk en voldoende dat y" of "x als en slechts als y". gezegden x, ja worden equivalentietermen genoemd.
De logische waarden van de equivalentiebewerking worden beschreven door de volgende waarheidstabel:

Gelijkwaardigheid speelt een belangrijke rol bij wiskundige bewijzen. Het is bekend dat een aanzienlijk aantal stellingen wordt geformuleerd in de vorm van noodzakelijke en voldoende voorwaarden, dat wil zeggen in de vorm van equivalentie. In dit geval, als we de waarheid of onwaarheid van een van de twee equivalentietermen kennen en de waarheid van de equivalentie zelf bewijzen, concluderen we dat de tweede equivalentieterm waar of onwaar is.

praktische taken

1. Bepaal de logische opbouw van de volgende zinnen en schrijf ze op in de taal van de propositielogica:

• Als het metaal wordt verwarmd, smelt het.
• Het is niet waar dat filosofische geschillen onoplosbaar zijn.
• Geld is een product van de spontane ontwikkeling van warenverhoudingen, en niet het resultaat van een overeenkomst of een andere bewuste handeling.

2. Schrijf de volgende uitspraken op in een logische formule:

a) als het buiten regent, dan moet je een paraplu meenemen of thuis blijven;

B) als - rechthoekig en de zijden gelijk zijn, dan

3. Controleer de waarheid van de stelling:

en als, .

b) als, .

c) als, .

4. Controleer de waarheid van de stelling:

a) Om morgen naar de les te gaan, moet ik vroeg opstaan. Als ik vandaag naar de bioscoop ga, ga ik laat naar bed. Als ik laat naar bed ga, word ik laat wakker. Daarom ga ik ofwel niet naar de bioscoop, of ik ga niet naar lessen.

b) Ik ga naar de bioscoop of naar het zwembad. Als ik naar de bioscoop ga, krijg ik esthetisch plezier. Als ik naar het zwembad ga, krijg ik lichamelijk plezier. Daarom, als ik lichamelijk genot krijg, zal ik geen esthetisch genot krijgen.

5 . Op de vraag: “Wie van de drie studenten heeft discrete wiskunde gestudeerd?” het juiste antwoord werd ontvangen: "Als hij de eerste bestudeerde, bestudeerde hij de derde, maar het is niet waar dat als hij de tweede bestudeerde, hij de derde bestudeerde." Wie heeft discrete wiskunde gestudeerd?

6. Bepaal wie van de vier studenten het examen heeft gehaald, indien bekend:

als de eerste geslaagd is, is de tweede geslaagd;

als de tweede geslaagd is, dan is de derde geslaagd of de eerste niet geslaagd;

als de vierde niet geslaagd is, dan is de eerste geslaagd en de derde niet geslaagd;

als de vierde geslaagd was, dan was de eerste geslaagd.

testvragen

1. Welke elementen zijn opgenomen in de taal van de logica?

2. Welke manieren ken je om de geldigheid van een logische formule vast te stellen?

Bibliografie

Oefening #10-11

Programma thema: Propositionele algebra formules.

Eigenschappen

Overweeg verschillende eigenschappen van het cartesiaanse product:

1. Als EEN,B zijn eindige verzamelingen, dan EEN× B- laatste. En omgekeerd, als een van de vermenigvuldigingssets oneindig is, dan is het resultaat van hun product een oneindige set.

2. Het aantal elementen in het Cartesiaanse product is gelijk aan het product van het aantal elementen van de vermenigvuldigingssets (als ze eindig zijn natuurlijk): | EEN× B|=|EEN|⋅|B| .

3. een np ≠(Een) p- in het eerste geval is het raadzaam om het resultaat van het cartesiaanse product te beschouwen als een matrix met afmetingen 1× np, in de tweede - als een matrix van maten n× p .

4. De commutatieve wet is niet vervuld, omdat de paren elementen van het resultaat van het cartesiaanse product zijn geordend: EEN× B≠B× EEN .

5. Er wordt niet voldaan aan de associatiewet: ( EEN× B)× C≠EEN×( B× C) .

6. Er is distributiviteit met betrekking tot basisbewerkingen op verzamelingen: ( EEN∗B)× C=(EEN× C)∗(B× C),∗∈{∩,∪,∖}

11. Het concept van een uiting. Elementaire en samengestelde uitspraken.

uitspraak is een uitspraak of declaratieve zin waarvan kan worden gezegd dat deze waar (T-1) of onwaar (L-0) is, maar niet beide tegelijk.

Bijvoorbeeld: "Het regent vandaag", "Ivanov voltooide laboratoriumwerk nr. 2 in de natuurkunde."

Als we verschillende initiële uitspraken hebben, dan van hen met behulp van logische vakbonden of deeltjes we kunnen nieuwe uitspraken vormen waarvan de waarheidswaarde alleen afhangt van de waarheidswaarden van de oorspronkelijke uitspraken en van de specifieke voegwoorden en deeltjes die deelnemen aan de constructie van de nieuwe uitspraak. De woorden en uitdrukkingen "en", "of", "niet", "als...dan", "daarom", "als en slechts dan" zijn voorbeelden van dergelijke voegwoorden. De originele verklaringen worden genoemd gemakkelijk , en nieuwe uitspraken die daaruit zijn geconstrueerd met behulp van bepaalde logische vakbonden - bestanddeel . Natuurlijk heeft het woord "eenvoudig" niets te maken met de essentie of structuur van de oorspronkelijke uitspraken, die zelf behoorlijk ingewikkeld kunnen zijn. In deze context is het woord "simpel" synoniem met het woord "origineel". Het belangrijkste is dat de waarheidswaarden van eenvoudige proposities bekend of gegeven zijn; ze worden in ieder geval op geen enkele manier besproken.

Hoewel een uitspraak als "Vandaag is geen donderdag" niet bestaat uit twee verschillende eenvoudige uitspraken, wordt het voor de uniformiteit van de constructie ook behandeld als een samengestelde, aangezien de waarheidswaarde wordt bepaald door de waarheidswaarde van een andere uitspraak "Vandaag is het donderdag "

Voorbeeld 2 De volgende uitspraken worden behandeld als samengestelde uitspraken:

Ik las Moskovsky Komsomolets en ik las Kommersant.

Als hij het zegt, dan is het waar.

De zon is geen ster.

Als het zonnig is en de temperatuur boven de 25 ° komt, kom ik met de trein of auto

Eenvoudige uitingen die zijn opgenomen in samengestelde uitingen kunnen zelf volledig willekeurig zijn. In het bijzonder kunnen ze zelf samengesteld zijn. De basistypen samengestelde uitspraken die hieronder worden beschreven, zijn onafhankelijk van de eenvoudige uitspraken waaruit ze bestaan, gedefinieerd.

12. Bewerkingen op afschriften.

1. ontkenning operatie.

De ontkenning van de verklaring MAAR ( leest "niet MAAR"," het is niet waar dat MAAR"), wat waar is wanneer MAAR vals en vals wanneer? MAAR- WAAR.

Negatieve uitspraken MAAR en genaamd tegenover.

2. combinatie operatie.

voegwoord uitspraken MAAR en BIJ heet een verklaring een B(lezen " MAAR en BIJ”), waarvan de ware betekenis wordt bepaald als en slechts als beide uitspraken MAAR en BIJ WAAR.

De conjunctie van proposities wordt het logische product genoemd en wordt vaak aangeduid als AB.

Laat de verklaring MAAR– “in maart is de luchttemperatuur van 0 naar + 7 C» en zeggen BIJ- "Het regent in Vitebsk." Dan een B zal als volgt zijn: “in maart is de luchttemperatuur van 0 naar + 7 C en het regent in Vitebsk." Dit voegwoord is waar als er uitspraken zijn MAAR en BIJ WAAR. Als blijkt dat de temperatuur lager was 0 of er was geen regen in Vitebsk, dan? een B zal vals zijn.

3 . disjunctie operatie.

disjunctie uitspraken MAAR en BIJ heet een verklaring een B (MAAR of BIJ), wat waar is als en slechts als ten minste één van de beweringen waar en onwaar is - wanneer beide beweringen onwaar zijn.

De disjunctie van proposities wordt ook wel de logische som genoemd A+B.

de verklaring " 4<5 of 4=5 ' is waar. Sinds de verklaring " 4<5 " is waar, en de verklaring " 4=5 ' is vals, dan een B is een echte verklaring 4 5 ».

4 . implicatie operatie.

implicatie uitspraken MAAR en BIJ heet een verklaring een B("indien MAAR, dan BIJ", "van MAAR zou moeten BIJ”), waarvan de waarde onwaar is als en slechts als MAAR waar, en BIJ vals.

In de implicatie een B uitspraak MAAR genaamd fundament, of verzenden, en de verklaring BIJ – gevolg, of conclusie.

13. Tabellen met de waarheid van uitspraken.

Een waarheidstabel is een tabel die een overeenkomst tot stand brengt tussen alle mogelijke sets van logische variabelen die in een logische functie zijn opgenomen en de waarden van de functie.

Waarheidstabellen worden gebruikt voor:

Het berekenen van de waarheid van complexe uitspraken;

Het vaststellen van de gelijkwaardigheid van uitspraken;

Definities van tautologieën.

Het vaststellen van de waarheid van complexe uitspraken.

voorbeeld 1 Bepaal de waarheid van de uitspraak C

Beslissing. De samenstelling van een complexe verklaring omvat 3 eenvoudige verklaringen: A, B, C. De kolommen in de tabel zijn gevuld met waarden (0, 1). Alle mogelijke situaties worden aangegeven. Eenvoudige zinnen worden van complexe zinnen gescheiden door een dubbele verticale lijn.
Bij het samenstellen van de tabel moet ervoor worden gezorgd dat de volgorde van acties niet wordt verward; als je de kolommen vult, moet je "van binnen naar buiten" bewegen, d.w.z. van elementaire formules tot steeds complexere; de laatste kolom die moet worden ingevuld, bevat de waarden van de oorspronkelijke formule.

MAAR	BIJ	Met		A+		· MET

De tabel laat zien dat deze bewering alleen waar is als A=0, B=1, C=1. In alle andere gevallen is het onwaar.

14. Gelijkwaardige formules.

Twee formules MAAR en BIJ worden equivalent genoemd als ze dezelfde logische waarden aannemen voor elke reeks waarden van de elementaire proposities die in de formule zijn opgenomen.

Gelijkwaardigheid wordt aangegeven door het teken "". Voor de transformatie van formules in equivalente, wordt een belangrijke rol gespeeld door de basisequivalenties, het uitdrukken van sommige logische bewerkingen door andere, equivalenten, die de basiswetten van de algebra van de logica uitdrukken.

Voor alle formules MAAR, BIJ, Met gelijkwaardigheid is geldig.

I. Basisequivalenten

wet van idempotentie

1-waar

0-false

Wet van tegenstrijdigheid

Wet van de uitgesloten midden

absorptiewet

formules splitsen

bindende wet

II. Equivalenties die sommige logische bewerkingen uitdrukken in termen van andere.

de wet van Morgan

III. Equivalenties die de basiswetten van de algebra van de logica uitdrukken.

Commutatieve wet

associatieve wet

distributieve wet

15. Formules van propositielogica.

Soorten formules in de klassieke propositielogica- in de propositielogica worden de volgende typen formules onderscheiden:

1. De wetten(identiek ware formules) - formules die, voor elke interpretatie van propositievariabelen, de waarde aannemen "WAAR";

2. tegenstellingen(identiek valse formules) - formules die, voor elke interpretatie van propositievariabelen, de waarde aannemen "vals";

3. Bevredigende formules- degenen die de betekenis aannemen "WAAR" voor ten minste één set waarheidswaarden van de propositievariabelen die erin zijn opgenomen.

Basiswetten van de klassieke propositielogica:

1. Identiteitsrecht: ;

2. De wet van tegenspraak: ;

3. Wet van het uitgesloten midden: ;

4. De wetten van commutativiteit en: , ;

5. De wetten van distributiviteit zijn relatief aan , en vice versa: , ;

6. De wet van verwijdering van de ware term van de conjunctie: ;

7. De wet van het verwijderen van de valse term van de disjunctie: ;

8. Wet van contrapositie: ;

9. Wetten van wederzijdse uitdrukbaarheid van propositionele connectieven: , , , , , .

Afwikkelbaarheidsprocedure- een methode waarmee voor elke formule kan worden vastgesteld of het een wet, een contradictie of een haalbare formule is. De meest gebruikelijke procedure voor afwikkelbaarheid is de waarheidstabelmethode. Hij is echter niet de enige. Een efficiënte methode van afwikkelbaarheid is de methode normale vormen voor propositielogische formules. normale vorm propositielogica formule is een vorm die het implicatieteken "" niet bevat. Er zijn conjunctieve en disjunctieve normaalvormen. De conjunctieve vorm bevat alleen de voegwoordtekens "". Als een formule gereduceerd tot conjunctieve normaalvorm een ​​subformule van de vorm bevat, dan is de hele formule in dit geval tegenstrijdigheid. De disjunctieve vorm bevat alleen disjunctietekens "". Als een formule gereduceerd tot disjunctieve normaalvorm een ​​subformule van de vorm bevat, dan is de hele formule in dit geval wet. In alle andere gevallen is de formule bevredigende formule:.

16. Predikaten en bewerkingen daarop. Kwantificatoren.

Een zin die een of meer variabelen bevat en die, voor specifieke waarden van de variabelen, een statement is, heet propositievorm of predikaat.

Afhankelijk van het aantal variabelen dat in het voorstel is opgenomen, worden enkelvoudig, dubbel, drievoudig enz. onderscheiden. predikaten respectievelijk aangeduid: A( X), BIJ( X, Bij), MET( X, Bij, z).

Als er een predikaat is gegeven, zijn er twee verzamelingen aan verbonden:

1. Set (domein) van definitie X, bestaande uit alle waarden van variabelen, wanneer ze in een predikaat worden vervangen, verandert de laatste in een verklaring. Bij het specificeren van een predikaat wordt het bereik ervan meestal gespecificeerd.

2. De waarheid set T, bestaande uit al die waarden van de variabelen, wanneer ze in het predikaat worden vervangen, wordt een ware verklaring verkregen.

De waarheidsverzameling van een predikaat is altijd een deelverzameling van zijn domein, d.w.z. .

U kunt dezelfde bewerkingen uitvoeren op predikaten als op uitspraken.

1. Ontkenning predikaat A( X) gedefinieerd op de verzameling X wordt het predikaat true genoemd voor die waarden waarvoor het predikaat A( X) verandert in een valse verklaring, en vice versa.

Uit deze definitie volgt dat de predikaten A( X) en B( X) zijn geen ontkenningen van elkaar als er minstens één waarde is waarvoor de predikaten A( X) en B( X) omzetten in proposities met dezelfde waarheidswaarden.

De waarheidsverzameling van het predikaat is de aanvulling op de waarheidsverzameling van het predikaat A( X). Geef met TA de waarheidsverzameling van het predikaat A( X), en via T - de waarheidsverzameling van het predikaat . Dan .

2. voegwoord predikaten A( X) en B( XX) BIJ( X X X, waaronder beide predikaten in ware uitspraken veranderen.

De waarheidsverzameling van de conjunctie van predikaten is het snijpunt van de waarheidsverzamelingen van het predikaat A( X) BIJ( X). Als we de waarheidsverzameling van het predikaat A(x) aangeven door TA, en de waarheidsverzameling van het predikaat B(x) door T B en de waarheidsverzameling van het predikaat A(x) B(x) door , dan

3. disjunctie predikaten A( X) en B( X) gedefinieerd op de verzameling X heet het predikaat A( X) BIJ( X), die verandert in een echte propositie voor die en alleen die waarden X X, waaronder ten minste één van de predikaten een ware uitspraak is geworden.

De waarheidsverzameling van een disjunctie van predikaten is de vereniging van de waarheidsverzamelingen van de predikaten die het vormen, d.w.z. .

4.implicatie predikaten A( X) en B( X) gedefinieerd op de verzameling X heet het predikaat A( X) BIJ( X), wat onwaar is voor die en alleen die waarden van de variabele waarvoor het eerste predikaat waar wordt en de tweede onwaar.

De waarheidsverzameling van de implicatie van predikaten is de vereniging van de waarheidsverzameling van het predikaat B( X) met toevoeging aan de waarheidsverzameling van het predikaat A( X), d.w.z.

5. Gelijkwaardigheid predikaten A( X) en B( X) gedefinieerd op de set X wordt een predikaat genoemd dat verandert in een ware verklaring voor al die en alleen die waarden van de variabele waarvoor beide predikaten in echte verklaringen of valse verklaringen veranderen.

De waarheidsverzameling van het equivalent van predikaten is het snijpunt van de waarheidsverzameling van het predikaat met de waarheidsverzameling van het predikaat.

Kwantificatorbewerkingen op predikaten

Een predikaat kan worden vertaald in een statement door de substitutiemethode en door de "quantifier hanging" -methode.

Over de nummers 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 kun je zeggen: a) alle gegeven getallen zijn priemgetallen; b) sommige van de gegeven getallen zijn even.

Omdat van deze zinnen kan worden gezegd dat ze waar of onwaar zijn, zijn de resulterende zinnen proposities.

Als we het woord "alle" uit zin "a" en het woord "sommige" uit zin "b" verwijderen, dan krijgen we de volgende predikaten: "deze getallen zijn priemgetallen", "deze getallen zijn oneven".

De woorden "alle" en "sommige" worden kwantoren genoemd. Het woord "quantifier" is van Latijnse oorsprong en betekent "hoeveel", dat wil zeggen, de quantifier geeft aan hoeveel (alle of enkele) objecten in een bepaalde zin worden genoemd.

Er zijn twee hoofdtypen kwantoren: de algemene kwantor en de existentiële kwantor.

voorwaarden "elke", "elke", "iedereen" worden genoemd – universele kwantor. Toegewezen .

Laat A( X) is een bepaald predikaat gegeven op de verzameling X. Onder de uitdrukking A( X) we zullen begrijpen dat de bewering waar is wanneer A( X) is waar voor elk element van de verzameling X, en anders onwaar. R .

In voorbeeld 1 voor R1 domein van definitie: , set van waarden - . Voor R2 domein van definitie: , reeks waarden: .

In veel gevallen is het handig om een ​​grafische weergave van een binaire relatie te gebruiken. Het wordt op twee manieren uitgevoerd: met behulp van punten op het vliegtuig en met behulp van pijlen.

In het eerste geval worden als horizontale en verticale as twee onderling loodrechte lijnen gekozen. Leg op de horizontale as de elementen van de set EEN en trek een verticale lijn door elk punt. Leg op de verticale as de elementen van de set B trek een horizontale lijn door elk punt. De snijpunten van de horizontale en verticale lijnen geven de elementen van het directe product weer

18. Methoden voor het instellen van binaire relaties.

Elke subset van het cartesiaanse product A × B wordt een binaire relatie genoemd die is gedefinieerd op een paar sets A en B (in het Latijn betekent "bis" "tweemaal"). In het algemene geval kan men, naar analogie met binaire relaties, n-aire relaties ook beschouwen als geordende rijen van n elementen uit een van de n verzamelingen.

Het symbool R wordt gebruikt om een ​​binaire relatie aan te duiden. Aangezien R een deelverzameling is van de verzameling A×B, kunnen we R⊆A× schrijven. Als het nodig is om aan te geven dat (a, b) ∈ R, d.w.z. er is een relatie R tussen de elementen a ∈ A en b ∈ B, schrijf dan aRb.

Manieren om binaire relaties te specificeren:

1. Dit is het gebruik van de regel, volgens welke alle elementen in deze relatie worden aangegeven. In plaats van een regel kun je de elementen van een gegeven relatie opsommen door ze direct op te sommen;

2. Tabel, in de vorm van grafieken en met behulp van secties. De basis van de tabelmethode is een rechthoekig coördinatensysteem, waarbij elementen van een verzameling langs één as worden uitgezet en elementen van een andere verzameling langs de tweede. De snijpunten van de coördinaten vormen punten die de elementen van het cartesiaanse product aanduiden.

Op (figuur 1.16) wordt het coördinatenraster voor verzamelingen getoond. De snijpunten van drie verticale lijnen met zes horizontale komen overeen met de elementen van de verzameling A×B. De cirkels op het raster markeren de elementen van de relatie aRb, waarbij a A en b ∈ B, R staat voor de “verdeelt” relatie.

Binaire relaties worden gegeven door tweedimensionale coördinatenstelsels. Het is duidelijk dat alle elementen van het cartesiaanse product van drie verzamelingen op dezelfde manier kunnen worden weergegeven in een driedimensionaal coördinatensysteem, vier verzamelingen in een vierdimensionaal systeem, enz.;

3. De methode van het specificeren van relaties met behulp van secties wordt minder vaak gebruikt, dus we zullen het niet overwegen.

19. Reflexiviteit van een binaire relatie. Voorbeeld.

In de wiskunde wordt een binaire relatie op een set reflexief genoemd als elk element van deze set in relatie staat tot zichzelf.

De eigenschap van reflexiviteit voor gegeven relaties door een matrix wordt gekenmerkt door het feit dat alle diagonale elementen van de matrix gelijk zijn aan 1; voor gegeven relaties door de grafiek heeft elk element een lus - een boog (x, x).

Als voor geen enkel element van de verzameling aan deze voorwaarde wordt voldaan, wordt de relatie antireflexief genoemd.

Als de antireflexieve relatie wordt gegeven door een matrix, dan zijn alle diagonale elementen nul. Wanneer een dergelijke relatie wordt gegeven door een grafiek, heeft elk hoekpunt geen lus - er zijn geen bogen van de vorm (x, x).

Formeel wordt de antireflexiviteit van een relatie gedefinieerd als: .

Als niet voor alle elementen van de verzameling aan de voorwaarde van reflexiviteit is voldaan, wordt gezegd dat de relatie niet-reflexief is.

©2015-2019 site
Alle rechten behoren toe aan hun auteurs. Deze site claimt geen auteurschap, maar biedt gratis gebruik.
Aanmaakdatum pagina: 2016-04-12