Des articles

1.2 : Propositions et logique


La logique est, fondamentalement, l'étude du raisonnement valide. Après avoir exploré cette forme de logique, nous examinerons les arguments logiques et comment nous pouvons déterminer la validité d'une affirmation.

Logique booléenne

On peut souvent classer les objets comme appartenant à des ensembles. Si vous alliez à la bibliothèque pour chercher un livre et qu'on vous demandait d'exprimer votre recherche en utilisant des unions, des intersections et des compléments d'ensembles, cela vous semblerait un peu étrange. Au lieu de cela, nous utilisons généralement des mots comme « et », « ou » et « non » pour connecter nos mots-clés ensemble afin de former une recherche. Ces mots, qui forment la base de la logique booléenne, sont directement liés à nos opérations ensemblistes. (La logique booléenne a été développée par le mathématicien anglais du XIXe siècle George Boole.)

Logique booléenne

La logique booléenne combine plusieurs déclarations vraies ou fausses en une expression vraie ou fausse.

En ce qui concerne les ensembles, une recherche est vraie si l'élément fait partie de l'ensemble.

Supposons que M soit l'ensemble de tous les livres de mystère et C soit l'ensemble de tous les livres de comédie. Si nous cherchons « mystère », nous recherchons tous les livres qui sont un élément de l'ensemble M ; la recherche est vraie pour les livres qui sont dans l'ensemble.

Lorsque nous cherchons « mystère et comédie », nous cherchons un livre qui soit un élément des deux ensembles, à l'intersection. Si nous cherchions « mystère ou comédie », nous cherchons un livre qui soit un mystère, une comédie, ou les deux, qui soit l'union des décors. Si nous avons recherché "pas de comédie", nous recherchons n'importe quel livre dans la bibliothèque qui n'est pas une comédie, le complément de l'ensemble C.

Connexion aux opérations d'ensemble

Éléments A et B dans l'intersection A B

A ou B éléments dans l'union A ⋃ B

pas des éléments A dans le complément Ac

Remarquez ici que ou alors n'est pas exclusif. C'est une différence entre l'utilisation logique booléenne du mot et l'utilisation quotidienne courante. Lorsque votre partenaire demande « Voulez-vous aller au parc ou au cinéma ? » ils proposent généralement un choix exclusif – une option ou l'autre, mais pas les deux. Dans la logique booléenne, le ou alors n'est pas exclusif - c'est plutôt comme si on lui demandait dans un restaurant "voulez-vous des frites ou alors un verre avec ça ? Répondre « les deux, s'il vous plaît » est une réponse acceptable.

Exemple (PageIndex{1})

Supposons que nous recherchions une base de données de bibliothèque pour les universités mexicaines. Exprimez une recherche raisonnable en utilisant la logique booléenne.

Solution

Nous pourrions commencer par la recherche « Mexique et université », mais nous serions susceptibles de trouver des résultats pour l'État américain du Nouveau-Mexique. Pour en tenir compte, nous pourrions réviser notre recherche pour lire :

Mexique et Université ne pas "Nouveau Mexique"

Dans la plupart des moteurs de recherche Internet, il n'est pas nécessaire d'inclure le mot et; le moteur de recherche suppose que si vous fournissez deux mots-clés, vous recherchez les deux. Dans la recherche de Google, le mot-clé ou alors doit être en majuscule OU, et un signe négatif devant un mot est utilisé pour indiquer ne pas. Les guillemets autour d'une phrase indiquent que la phrase entière doit être recherchée. La recherche de l'exemple précédent sur Google pourrait s'écrire :

Université du Mexique - « Nouveau-Mexique »

Exemple (PageIndex{2})

Décrivez les nombres qui remplissent la condition : pair et inférieur à 10 et supérieur à 0

Solution

Les nombres qui satisfont aux trois exigences sont {2, 4, 6, 8}

Parfois, les déclarations faites en anglais peuvent être ambiguës. Pour cette raison, la logique booléenne utilise des parenthèses pour montrer les précédents, tout comme dans l'ordre algébrique des opérations.

Exemple (PageIndex{3})

Décrivez les nombres qui remplissent la condition : nombre impair et inférieur à 20 et supérieur à 0 et (multiple de 3 ou multiple de 5)

Solution

Les trois premières conditions nous limitent à l'ensemble {1, 3, 5, 7, 9, 11, 13, 15, 17, 19}

Les dernières conditions groupées nous disent de trouver des éléments de cet ensemble qui sont aussi soit un multiple de 3 soit un multiple de 5. Cela nous laisse avec l'ensemble {3, 5, 9, 15}

Notez que nous aurions obtenu un résultat très différent si nous avions écrit (nombre impair et inférieur à 20 et supérieur à 0 et multiple de 3) ou multiple de 5

Le premier ensemble groupé de conditions donnerait {3, 9, 15}. Lorsqu'il est combiné avec la dernière condition, cependant, cet ensemble s'étend sans limites :

{3, 5, 9, 15, 20, 25, 30, 35, 40, 45, …}

Exemple (PageIndex{4})

L'expression anglaise « Allez au magasin et achetez-moi des œufs et des bagels ou des céréales » est ambiguë ; il n'est pas clair si les demandeurs demandent toujours des œufs avec des bagels ou des céréales, ou s'ils demandent soit la combinaison d'œufs et de bagels, soit simplement des céréales.

Solution

Pour cette raison, l'utilisation de parenthèses clarifie l'intention :

ufs et (bagels ou céréales) signifie Option 1 : ufs et bagels, Option 2 : ufs et céréales

(Eufs et bagels) ou céréales signifie Option 1 : ufs et bagels, Option 2 : Céréales

Sachez que lorsqu'une chaîne de conditions est écrite sans symboles de regroupement, elle est souvent interprétée de gauche à droite, ce qui entraîne cette dernière interprétation.

Expressions conditionnelles

Au-delà de la recherche, la logique booléenne est couramment utilisée dans les tableurs comme Excel pour effectuer des calculs conditionnels. Une déclaration est quelque chose qui est vrai ou faux. Une déclaration comme 3 < 5 est vraie ; une déclaration comme « un rat est un poisson » est fausse. Une déclaration comme « x < 5 » est vraie pour certaines valeurs de x et fausse pour d'autres. Lorsqu'une action ou un résultat dépend de la valeur d'une déclaration, cela forme un conditionnel.

Déclarations et conditions

Un énoncé est soit vrai, soit faux. Un conditionnel est un énoncé composé de la forme « si p alors q » ou « si p alors q, sinon s ».

Exemple (PageIndex{5})

Dans le langage courant, un exemple d'énoncé conditionnel serait « S'il pleut, alors nous irons au centre commercial. Sinon, nous irons faire une randonnée.

Solution

L'énoncé « S'il pleut » est la condition – cela peut être vrai ou faux pour un jour donné. Si la condition est vraie, alors nous suivrons le premier plan d'action et irons au centre commercial. Si la condition est fausse, alors nous utiliserons l'alternative et partirons en randonnée.

Exemple (PageIndex{6})

Comme mentionné précédemment, les instructions conditionnelles sont couramment utilisées dans les tableurs comme Excel ou Google Sheets.

Dans Excel, vous pouvez saisir une expression telle que =IF(A1<2000, A1+1, A1*2)

Solution

Notez qu'après le FI, il y a trois parties. La première partie est la condition, et les deux autres sont des calculs. Excel examinera la valeur de la cellule A1 et la comparera à 2000. Si cette condition est vraie, le premier calcul est utilisé et 1 est ajouté à la valeur de A1 et le résultat est stocké. Si la condition est fausse, alors le deuxième calcul est utilisé, et A1 est multiplié par 2 et le résultat est stocké.

En d'autres termes, cette déclaration équivaut à dire « Si la valeur de A1 est inférieure à 2000, alors ajoutez 1 à la valeur de A1. Sinon, multipliez A1 par 2".

Exemple (PageIndex{7})

L'expression =SI(A1>5, 2*A1, 3*A1) est utilisée. Trouvez le résultat si A1 est 3, et le résultat si A1 est 8.

Solution

Cela équivaut à dire

Si A1 > 5, calculez 2*A1. Sinon, calculez 3*A1

Si A1 est 3, alors la condition est fausse, puisque 3 > 5 n'est pas vrai, donc nous faisons l'action alternative, et multiplions par 3, donnant 3*3 = 9

Si A1 est 8, alors la condition est vraie, puisque 8 > 5, donc on multiplie la valeur par 2, donnant 2*8=16

Exemple (PageIndex{8})

Un comptable doit retenir 15 % du revenu pour les impôts si le revenu est inférieur à 30 000 $, et 20 % du revenu si le revenu est de 30 000 $ ou plus. Écrivez une expression qui calculerait le montant à retenir.

Solution

Notre conditionnel doit comparer la valeur à 30 000. Si le revenu est inférieur à 30 000, il faut calculer 15 % du revenu : 0,15*revenu. Si le revenu est supérieur à 30 000, il faut calculer 20 % du revenu : 0,20*revenu.

En mots, nous pourrions écrire « Si revenu < 30 000, alors multipliez par 0,15, sinon multipliez par 0,20 ». Dans Excel, on écrirait :

=SI(A1<30000, 0,15*A1, 0,20*A1)

Comme nous l'avons fait précédemment, nous pouvons créer des conditions plus complexes en utilisant les opérateurs et, ou, et ne pas réunir des conditions plus simples.

Exemple (PageIndex{9})

Un parent pourrait dire à son enfant « si vous nettoyez votre chambre et sortez les poubelles, vous pouvez avoir de la crème glacée ».

Ici, il y a deux conditions plus simples :

1) L'enfant nettoie sa chambre

2) L'enfant sort les poubelles

Solution

Étant donné que ces conditions ont été jointes à et, le conditionnel combiné ne sera vrai que si les deux conditions plus simples sont vraies ; si l'une des tâches n'est pas terminée, la condition du parent n'est pas remplie.

Notez que si le parent avait dit « si vous nettoyez votre chambre ou sortez les poubelles, alors vous pouvez avoir de la crème glacée », alors l'enfant n'aurait besoin d'effectuer qu'une seule tâche pour remplir la condition.

Supposons que vous vouliez que quelque chose se produise lorsqu'une certaine valeur est comprise entre 100 et 300. Pour créer la condition "A1 < 300 et A1 > 100" dans Excel, vous devez entrer "AND(A1<300, A1>100)" . De même, pour la condition « A1=4 ou A1=6 », vous devez saisir « OU(A1=4, A1=6) »

Exemple (PageIndex{10})

Dans une feuille de calcul, la cellule A1 contient le revenu annuel et A2 contient le nombre de personnes à charge.

Un certain crédit d'impôt s'applique si une personne sans personne à charge gagne moins de 10 000 $, ou si une personne avec des personnes à charge gagne moins de 20 000 $. Écrivez une règle qui décrit cela.

Solution

La règle est respectée de deux manières :

le revenu est inférieur à 10 000 et les personnes à charge sont de 0, ou

le revenu est inférieur à 20 000 et les personnes à charge ne sont pas 0.

De manière informelle, nous pourrions les écrire comme

(A1 < 10000 et A2 = 0) ou (A1 < 20000 et A2 > 0)

Au format Excel, on écrirait

SI(OU(ET(A1<10000, A2=0), ET(A1<20000, A2>0)), "vous remplissez les conditions", "vous ne remplissez pas les conditions")

Déclarations quantifiées

Les mots qui décrivent un ensemble entier, tels que « tous », « tous » ou « aucun », sont appelés quantificateurs universels parce que cet ensemble pourrait être considéré comme un ensemble universel. En revanche, des mots ou des expressions tels que « certains », « un » ou « au moins un » sont appelés quantificateurs existentiels car ils décrivent l'existence d'au moins un élément dans un ensemble.

Quantificateurs

UNE quantificateur universel déclare qu'un ensemble entier de choses partagent une caractéristique.

Une quantificateur existentiel indique qu'un ensemble contient au moins un élément.

Quelque chose d'intéressant se produit lorsque nous nions – ou affirmons le contraire – une affirmation quantifiée.

Exemple (PageIndex{11})

Supposons que votre ami dise « Tout le monde triche sur ses impôts ». Quelle est la quantité minimale de preuves dont vous auriez besoin pour prouver que votre ami a tort ?

Solution

Pour montrer qu'il n'est pas vrai que tout le monde triche sur ses impôts, il suffit d'une personne qui ne triche pas sur ses impôts. Ce serait parfaitement bien de produire plus de personnes qui ne trichent pas, mais un contre-exemple est tout ce dont vous avez besoin.

Il est important de noter que vous n'avez pas besoin de montrer qu'absolument personne ne triche sur ses impôts.

Exemple (PageIndex{12})

Supposons que votre ami dise « L'un de ces six cartons de lait fuit ». Quelle est la quantité minimale de preuves dont vous auriez besoin pour prouver que votre ami a tort ?

Solution

Dans ce cas, vous devrez vérifier les six cartons et montrer qu'aucun d'entre eux ne fuit. Vous ne pouvez pas réfuter la déclaration de votre ami en ne cochant qu'un seul des cartons.

Lorsque nous nions une déclaration avec un quantificateur universel, nous obtenons une déclaration avec un quantificateur existentiel, et vice-versa.

Nier un énoncé quantifié

La négation de "tous les A sont B" est "au moins un A n'est pas B".

La négation de "aucun A n'est B" est "au moins un A est B".

La négation de "au moins un A est B" est "aucun A n'est B".

La négation de "au moins un A n'est pas B" est "tous les A sont B".

Exemple (PageIndex{13})

"Quelqu'un a apporté une lampe de poche." Écrivez la négation de cet énoncé.

Solution

La négation est "Personne n'a apporté de lampe de poche".

Exemple (PageIndex{14})

« Il n’y a pas de nombres premiers pairs. » Écrivez la négation de cet énoncé.

Solution

La négation est "Au moins un nombre premier est pair".

Essayez-le maintenant 1

  1. Écrivez la négation de « Tous les enfants islandais apprennent l'anglais à l'école ».

1.4 Propositions de logique et d'amp

C'est l'un des plus de 2400 cours sur OCW. Explorez les matériaux de ce cours dans les pages liées le long de la gauche.

MIT OpenCourseWare est une publication gratuite et ouverte de matériel provenant de milliers de cours du MIT, couvrant l'ensemble du programme du MIT.

Aucune inscription ni inscription. Parcourez et utilisez librement les documents OCW à votre rythme. Il n'y a pas d'inscription, ni de date de début ou de fin.

La connaissance est votre récompense. Utilisez OCW pour guider votre propre apprentissage tout au long de la vie ou pour enseigner aux autres. Nous n'offrons pas de crédit ou de certification pour l'utilisation d'OCW.

Fait pour le partage. Téléchargez des fichiers pour plus tard. Envoyez à vos amis et collègues. Modifier, remixer et réutiliser (n'oubliez pas de citer OCW comme source.)

À propos de MIT OpenCourseWare

MIT OpenCourseWare est une publication en ligne de documents de plus de 2 500 cours MIT, partageant librement des connaissances avec des apprenants et des éducateurs du monde entier. En savoir plus »

&copier 2001&ndash2018
Massachusetts Institute of Technology

Votre utilisation du site et du matériel MIT OpenCourseWare est soumise à notre licence Creative Commons et à d'autres conditions d'utilisation.


1.1.2 : Opérateurs logiques

  • Contribution de Stefan Hugtenburg et Neil Yorke-Smith
  • Faculté de l'Université de technologie de Delft
  • Provenant de TU Delft Open

Ce que nous faisons avec les propositions, c'est les combiner avec des opérateurs logiques, également appelés connecteurs logiques. Un opérateur logique peut être appliqué à une ou plusieurs propositions pour produire une nouvelle proposition. La valeur de vérité de la nouvelle proposition est entièrement déterminée par l'opérateur et par les valeurs de vérité des propositions auxquelles elle s'applique. En anglais, les opérateurs logiques sont représentés par des mots tels que &lsquoand&rsquo, &lsquoor&rsquo et &lsquonot&rsquo. Par exemple, la proposition &ldquoJe voulais partir et je suis parti&rdquo est formée de deux propositions plus simples jointes par le mot &lsquoand&rsquo. L'ajout du mot &lsquonot&rsquo à la proposition &ldquoI left&rdquo donne &ldquoI did not left&rdquo (après un peu d'ajustement grammatical nécessaire).

Mais l'anglais est un peu trop riche pour la logique mathématique. Quand vous lisez la phrase &ldquoJe voulais partir et je suis parti&rdquo, vous voyez probablement une connotation de causalité : je suis parti parce que je voulais partir. Cette implication ne découle pas de la combinaison logique des valeurs de vérité des deux propositions &ldquoI voulait laisser&rdquo et &ldquoI left&rdquo. Ou considérez la proposition &ldquo je voulais partir mais je ne suis pas parti&rdquo. Ici, le mot &lsquobut&rsquo a le même

sens logique comme le mot &lsquoand&rsquo, mais la connotation est très différente. Ainsi, en logique mathématique, nous utilisons des symboles pour représenter des opérateurs logiques. Ces symboles n'ont aucune connotation au-delà de leur signification logique définie. Les opérateurs logiques correspondant aux mots anglais &lsquoand&rsquo, &lsquoor&rsquo et &lsquonot&rsquo sont &and, &or et ¬.

Laisser p et q être des propositions. Puis p &ou alors q, p &et q, et pasp sont des propositions, dont les valeurs de vérité sont données par les règles :

&taureau p&etq est vrai quand les deux p est vrai et q est vrai, et dans aucun autre cas.
&taureau p&ou alorsq est vrai quand soit p est vrai, ou q est vrai, ou les deux p et q sont vrais, et dans aucun autre cas.
&taureau &pasp est vrai quand p est faux, et dans aucun autre cas.

Les opérateurs &and, &or et ¬ sont respectivement appelés conjonction, disjonction et négation. (Notez que p&etq est lu comme &lsquop et q&rsquo, p&ou alorsq est lu comme &lsquop ou alors q&rsquo, et &pasp est lu comme &lsquonot p&rsquo.)

Considérez la déclaration &ldquoJe suis un étudiant CSE ou je ne suis pas un étudiant TPM.&rdquo Prendre p pour signifier & ldquo je suis un étudiant du CSE & rdquo et q pour signifier &ldquoJe suis un étudiant TPM&rdquo, vous pouvez écrire ceci comme p &ou pasq.


Contenu

Et est généralement noté par un opérateur infixe : en mathématiques et en logique, il est noté ∧ , [1] [3] & ou alors × en électronique, et dans les langages de programmation, & , && , ou alors et . Dans la notation de préfixe de Jan Łukasiewicz pour la logique, l'opérateur est K, pour le polonais koniunkcja. [4]

Conjonction logique est une opération sur deux valeurs logiques, typiquement les valeurs de deux propositions, qui produit une valeur de vrai si et seulement si ses deux opérandes sont vrais. [2] [3]

L'identité conjonctive est vraie, c'est-à-dire que l'opération ET d'une expression avec vrai ne changera jamais la valeur de l'expression. Conformément au concept de vérité vide, lorsque la conjonction est définie comme un opérateur ou une fonction d'arité arbitraire, la conjonction vide (AND-ing sur un ensemble vide d'opérandes) est souvent définie comme ayant le résultat vrai.

Table de vérité Modifier

Défini par d'autres opérateurs Modifier

Dans les systèmes où la conjonction logique n'est pas une primitive, elle peut être définie comme [5]

En règle générale, l'introduction d'une conjonction est une forme d'argument classiquement valide et simple. La forme argumentative a deux prémisses, UNE et B. Intuitivement, il permet l'inférence de leur conjonction.

UNE, B. Donc, UNE et B.

Voici un exemple d'argument qui correspond à la forme introduction à la conjonction:

Bob aime les pommes. Bob aime les oranges. Par conséquent, Bob aime les pommes et Bob aime les oranges.

L'élimination de conjonction est une autre forme d'argument simple et classiquement valide. Intuitivement, il permet l'inférence à partir de n'importe quelle conjonction de l'un ou l'autre élément de cette conjonction.

UNE et B. Donc, UNE.

UNE et B. Donc, B.

Définition Modifier

Cette formule peut être considérée comme un cas particulier de

Autres stratégies de preuve Modifier

En d'autres termes, une conjonction peut en fait être prouvée fausse simplement en connaissant la relation de ses conjonctions, et pas nécessairement sur leurs valeurs de vérité.

Cette formule peut être considérée comme un cas particulier de

L'un ou l'autre des éléments ci-dessus sont des preuves constructivement valides par contradiction.

distributivité : avec diverses opérations, notamment avec ou alors

préservation de la vérité : oui
Lorsque toutes les entrées sont vraies, la sortie est vraie.

préservant le mensonge : oui
Lorsque toutes les entrées sont fausses, la sortie est fausse.

Non-linéarité : 1 (la fonction est pliée)

Si vous utilisez des valeurs binaires pour vrai (1) et faux (0), alors conjonction logique fonctionne exactement comme la multiplication arithmétique normale.

Dans la programmation informatique de haut niveau et l'électronique numérique, la conjonction logique est généralement représentée par un opérateur infixe, généralement sous la forme d'un mot-clé tel que " ET ", une multiplication algébrique ou le symbole esperluette & (parfois doublé comme dans && ). De nombreux langages fournissent également des structures de contrôle de court-circuit correspondant à la conjonction logique.

La conjonction logique est souvent utilisée pour les opérations au niveau du bit, où 0 correspond à faux et 1 à vrai :

L'opération peut également être appliquée à deux mots binaires considérés comme des chaînes de bits de longueur égale, en prenant le ET au niveau du bit de chaque paire de bits aux positions correspondantes. Par exemple:

Cela peut être utilisé pour sélectionner une partie d'une chaîne de bits à l'aide d'un masque de bits. Par exemple, 10011101 ET 00001000 = 00001000 extrait le cinquième bit d'une chaîne de bits de 8 bits.

Dans les réseaux informatiques, les masques de bits sont utilisés pour dériver l'adresse réseau d'un sous-réseau au sein d'un réseau existant à partir d'une adresse IP donnée, en ajoutant l'adresse IP et le masque de sous-réseau.

La conjonction logique " ET " est également utilisée dans les opérations SQL pour former des requêtes de base de données.

L'appartenance d'un élément d'un ensemble d'intersection en théorie des ensembles est définie en termes de conjonction logique : XUNEB si et seulement si (XUNE) ∧ (XB). Grâce à cette correspondance, l'intersection de la théorie des ensembles partage plusieurs propriétés avec la conjonction logique, telles que l'associativité, la commutativité et l'idempotence.

Comme pour les autres notions formalisées en logique mathématique, la conjonction logique et est lié à, mais pas le même que, la conjonction grammaticale et en langues naturelles.

L'anglais "et" a des propriétés qui ne sont pas capturées par la conjonction logique. Par exemple, "et" implique parfois un ordre ayant le sens de "alors". Par exemple, "Ils se sont mariés et ont eu un enfant" dans le discours courant signifie que le mariage est venu avant l'enfant.

Le mot "et" peut également impliquer une partition d'une chose en parties, comme "Le drapeau américain est rouge, blanc et bleu". Ici, cela ne veut pas dire que le drapeau est immediatement rouge, blanc et bleu, mais plutôt qu'il a une partie de chaque couleur.


Relations entre propositions : le carré des oppositions

Après avoir compris les bases de la prédication en termes de formes A, E, I et O, il y a un autre type de prédication très fondamental à commenter avant de passer à la compréhension des relations qui existent entre les différentes formes standard.

Lorsque nous avons parlé de prédication comme disant quelque chose à propos de quelque chose, nous avons oublié de faire très attention au fait que très souvent, le quelque chose dont nous disons quelque chose n'est pas un groupe d'au moins un ou un groupe de tous, parfois c'est juste une seule chose individuelle. Comme

Verizon est meilleur que Cingular ou alors

Stephen Colbert n'a pas inventé la "vérité".

Dans ces déclarations, le sujet est ce que nous appelons singulier, on les appelle donc singulier déclarations ou prédications. Plus tard dans ce cours, lorsque nous aurons quelques conventions symboliques appropriées avec lesquelles jouer, nous représenterons ce type de prédication comme unique. Mais pour le moment, travaillant sans rien en dehors de nos conventions linguistiques ordinaires, il est plus logique de les voir comme une sous-espèce, si vous voulez, de la prédication universelle.

Aucune chose identique à Pluton n'est une planète

a une sonorité assez étrange au début. Cela soulève la question immédiate : qu'entendez-vous par “chose identique à… ?” ? identique à lui-même et distinct de toute autre chose. Parlez de votre perspicacité, hein ? Pluton est identique à lui-même. Stephen Colbert est également identique à lui-même. Verizon est également identique à lui-même. Si vous pouvez voir cela, alors vous pouvez voir que " tous les membres de la classe des choses identiques à Stephen Colbert " est une autre façon de dire " Stephen Colbert ". vue de Logic, est que cette convention nous permet de représenter nos prédications sur Stephen Colbert, et de comprendre que tout ce qui est vrai à propos de n'importe quel UNE affirmation en tant que simple fonction de son caractère universel et affirmatif sera également vraie pour toutes les affirmations faites à propos de Stephen Colbert (et Pluton et Verizon).

Avec cette stratégie quelque peu inélégante de traitement des énoncés singuliers, il nous est possible de représenter tout prédication simple en tant que proposition catégorique, et pour l'adapter au format rigide :

Quantifère—Terme sujet—Copule—Terme prédicat.

Chaque énoncé ou prédication simple auquel vous pouvez penser est celui qu'il est possible de rendre sous l'une des quatre formes d'affirmatif universel, négatif universel, affirmatif particulier ou négatif particulier : A, E, I ou O.

Il est probable que l'envie de jouer de Léonard ait disparu au cours de ses années de maturité et ait été absorbée par son activité de recherche, qui représentait le dernier et suprême déploiement de sa personnalité. Freud, Léonard de Vinci et un souvenir de son enfance de L'étrange (Livres Pingouin)

Du point de vue de la logique catégorique, cela devient un UNE déclaration, dont le sujet est « des choses identiques à la pulsion de jeu de Léonard de Vinci ». Le prédicat peut être représenté comme le plus complexe : « des traits de personnalité qui ont disparu dans ses années de maturité, absorbés dans son activité de recherche, qui ont représenté le dernier et suprême déploiement de sa personnalité ».

Considérons maintenant les relations entre ces quatre modèles de prédication. Puisque chacun est caractérisé, lui-même, par deux termes descriptifs, et puisque nos quatre termes descriptifs sont en fait deux paires de termes de sens opposé, il est facile de repérer la relation entre deux ensembles de paires.

Rafraîchissez votre compréhension des termes descriptifs :

A et O ont la même relation que E et moi. L'un de chaque paire est universel, l'autre particulier et l'un de chaque paire est affirmatif, l'autre négatif. Le A et le O sont opposés dans les deux sens, il en va de même pour le E et le I. Intuitivement, on pourrait bien s'attendre à ce que cela ait des implications pour leurs valeurs de vérité : s'ils sont complètement opposés, alors sûrement si l'un d'eux est vrai, l'autre doit être faux. C'est en effet le cas, et la relation entre deux énoncés quelconques de ces formes (à propos du même sujet et des mêmes termes de prédicat) est appelé «Contradiction.”

Aucun rationaliste n'est empiriste T

Certains rationalistes sont des empiristes F

Tous les fondamentalistes sont athées F

Certains fondamentalistes ne sont pas athées T

Tous les maris ont des femmes T

Certains maris n'ont pas de femme F

Aucun avocat n'est philosophe F

Certains avocats sont des philosophes T

Il est de tradition de disposer le carré suivant, avec A et O aux coins opposés, et E et I aux autres coins opposés :

(Source : Encyclopédie de philosophie de Stanford)

Ce powerpoint avec narration vous guide à travers le même matériel que le texte vient de présenter et qui suit ensuite. J'espère que c'est utile.

La contradiction est représentée par les relations diagonales. Mais comme vous pouvez le voir, il y a de la place pour commenter les relations entre A et E, entre A et I, entre E et O, et entre I et O. Je pense à cela comme le Carré des Oppositions (avec un « s » ), bien que la plupart des livres de logique l'appellent le carré d'opposition (sans le "s"). Je préfère cela simplement parce qu'il y a des relations multiples, pas une seule, même si elles ne sont pas toutes affaire d'incompatibilité (ce que connote « opposition »). On peut même l'appeler le Carré des Propositions. Le nom est moins important que les relations que le carré attire notre attention :

Entre toutes les déclarations A et E sur le même sujet et les mêmes termes de prédicat, vous voyez que les deux sont universels, mais l'un est négatif, l'autre affirmatif. Pas complètement différents les uns des autres. Considérez les conséquences pour leurs valeurs de vérité, avec quelques exemples. En lisant ces affirmations, notez si chacune est vraie ou fausse et voyez ce que vous pouvez déterminer comme affirmation générale sur la relation entre A et E.

La relation A-E :

1 Aucun œuf parlant n'est impoli

2 Tous les œufs qui parlent sont impolis

3 Aucun pape n'est catholique

4 Tous les papes sont catholiques

5 Aucun sénateur n'est communiste

6 Tous les sénateurs sont communistes

7 Aucun sénateur n'est démocrate

8 Tous les sénateurs sont démocrates

Avant de commenter la relation A-E ici, permettez-moi de vous donner des exemples des trois autres. Voyez ce que vous pouvez trouver comme généralisations en considérant les modèles de compatibilité vérité-valeur que vous identifiez :

La relation A-I :

9 Tous les scientifiques cognitifs sont des neurobiologistes

10 Certains scientifiques cognitifs sont des neurobiologistes

11 Tous les athées sont agnostiques

12 Certains athées sont agnostiques

13 Toutes les clarinettes sont des trompettes

14 Certaines clarinettes sont des trompettes

La relation E-O :

15 Aucun comédien n'est chanteur

16 Certains comédiens ne sont pas des chanteurs

17 Aucun grand-père n'est la sœur de quelqu'un

18 Un grand-père n'est pas la sœur de quelqu'un

20 Certains poulets ne sont pas des oiseaux

La relation I-O :

21 Certains punk rockers sont des shoegazers

22 Certains punk rockers ne sont pas des shoegazers

23 Certains maris sont mariés

24 Certains maris ne sont pas mariés

25 Certains maris ont des femmes

26 Certains maris n'ont pas de femme

Réfléchissez à ces ensembles d'énoncés et à ce que vous savez de leurs valeurs de vérité. Pouvez-vous déterminer ce qui est toujours le cas, ce qui peut toujours être déduit lorsque l'un d'une paire A-E est vrai ? Faux?

Quand l'une des paires d'E-S est vraie ? Faux?

Quand l'un d'un Universel et d'un Particulier de même qualité (A-I, E-O) est Vrai ? Faux?

. Pour poursuivre, vous pouvez passer à la section suivante de ce chapitre sur la logique catégorique, intitulée « Terminer le carré et les inférences immédiates ».


Exercer

Identifiez lesquelles des phrases suivantes sont des conjonctions fonctionnelles de vérité. Si la phrase est une conjonction véri-fonctionnelle, identifiez les deux conjonctions (en les écrivant).

1. Jack et Jill sont des collègues.
2. Tom est pompier et père de famille.
3. Ringo Starr et John Lennon étaient des camarades de groupe.
4. Lucy adore les sandwichs au steak et à l'oignon.
5. Cameron Dias a eu plusieurs relations, bien qu'elle ne se soit jamais mariée.
6. Bob et Sally se sont embrassés.
7. Une personne qui joue à la fois de la mandoline et de la guitare est un multi-instrumentiste.
8. Personne n'a jamais contracté la rage et n'a jamais vécu.
9. Jack et Jill sont des cow-boys.
10. Josiah est néanmoins amish, il est aussi un trafiquant de drogue.
11. Les Tigers sont la meilleure équipe de baseball de l'État, mais ils ne sont pas aussi bons que les Yankees.
12. Bob est allé à la plage pour se reposer et se détendre.
13. Lauren n'est toujours pas la coureuse la plus rapide de l'équipe, elle est assez rapide pour avoir atteint le championnat national.
14. La bague est belle, mais chère.
15. C'est triste, mais vrai que beaucoup d'Américains ne savent pas d'où viendra leur prochain repas.

1 Certains philosophes prétendraient qu'une proposition n'est pas la même chose qu'un énoncé, mais les raisons pour le faire ne sont pas pertinentes pour ce que nous allons faire dans ce chapitre. Ainsi, pour nos besoins, nous pouvons traiter une proposition comme la même chose qu'un énoncé.


Problèmes résolus

Cliquez ou appuyez sur un problème pour voir la solution.

Exemple 1

Prouver les lois de De Morgan : [ eg left(

ight) equiv left( < eg p> ight) lor left( < eg q> ight),] [ eg left(

ight) equiv left( < eg p> ight) land left( < eg q> ight).]

Exemple 2

Montrez que l'instruction [s = left(

ight) lor left( < eg p land q> ight)] est une tautologie .

Exemple 3

Exemple 4

Exemple 5

  1. Nick va au gym (4) fois par semaine.
  2. Nicole va au gym (2) ou (3) fois par semaine.
  3. Max va au gym 2 fois par semaine, mais pas toutes les semaines.
  4. Amy va parfois au gymnase.
  5. Certaines personnes vont au gymnase tous les jours.
  6. Presque personne ne va à la salle de sport 15 fois par semaine.

Exemple 6

  1. Chaque élève suivra le calcul.
  2. Chaque élève suivra un cours de mathématiques.
  3. Lora prendra le calcul et l'algèbre linéaire.
  4. Il y a un cours que tout le monde va suivre.
  5. Il y a un cours que personne ne suivra.
  6. Tom suivra tous les cours de mathématiques à l'exception de la topologie.

Exemple 7

  1. (gauche < < – 27, – 8, – 1,0,1,8,27>droit>)
  2. (left< <2>> ormalsize, large<3>> ormalsize, large<4>> normalsize, large<5>> ormalsize, large<6>> ormalsize> ight>)
  3. (gauche < <5,8,13,21,34,55>droit>)

Exemple 1.

Prouver les lois de De Morgan : [ eg left(

ight) equiv left( < eg p> ight) lor left( < eg q> ight),] [ eg left(

ight) equiv left( < eg p> ight) land left( < eg q> ight).]

Nous vérifions le (1 exte) La loi de De Morgan utilisant la table de vérité.

On écrit d'abord toutes les combinaisons possibles des propositions (p) et (q.) Les négations de (p) et (q) sont leurs valeurs opposées. L'expression (p land q) est conjonction de (p) et (q.) On détermine alors la négation de la conjonction ( eg left(

droite)). L'expression (left( < eg p> ight) lor left( < eg q> ight)) est la disjonction de ( eg p) et ( eg q.)

On voit que les deux dernières colonnes de la table de vérité sont les mêmes. Cela prouve le (1 exte) La loi de De Morgan.

De même, nous pouvons vérifier le (2 ext) La loi de De Morgan :

Exemple 2.

Montrez que l'instruction [s = left(

ight) lor left( < eg p land q> ight)] est une tautologie .

Une tautologie est définie comme une proposition qui est toujours vraie. Nous créons donc une table de vérité pour l'énoncé et vérifions ses valeurs de vérité.

Les valeurs de (p,) (q,) ( eg p,) et ( eg q) sont faciles à remplir. La colonne suivante (

) signifie disjonction de (p) et ( eg q.) On trouve alors la conjonction (< eg p land q>.) L'énoncé final (s) est la disjonction de deux propositions précédentes .

Nous voyons que toutes les valeurs (4) dans la dernière colonne sont vraies. Par conséquent, l'instruction (s = left(

ight) lor left( < eg p land q> ight)) est une tautologie.

Exemple 3.

Une contradiction est une déclaration qui est toujours fausse. Construisons une table de vérité pour nous assurer que l'instruction (r) n'a que des valeurs fausses.

La première expression ( eg p land q) est la conjonction de ( eg p) et (q.) La deuxième expression (p leftrightarrow q) est le biconditionnel de (p) et (q). L'opération finale est la conjonction de deux propositions précédentes.

Une déclaration contradictoire

La dernière colonne ne contient que des fausses valeurs. Par conséquent, la proposition (r = ( eg p land q) land (p leftrightarrow q)) est une contradiction.

Exemple 4.

Nous construisons une table de vérité pour nous assurer que les côtés gauche et droit de l'énoncé sont équivalents.

et trouver les valeurs de vérité de (s1) et (s2.)

En appliquant les opérations de conjonction et de disjonction, nous obtenons le tableau suivant :


1.2 : Propositions et logique

La logique propositionnelle s'intéresse aux propositions et à leurs interrelations. La notion de proposition ici ne peut pas être définie avec précision. En gros, un proposition est une condition possible du monde qui est soit vraie soit fausse, par ex. la possibilité qu'il pleuve, la possibilité qu'il fasse nuageux, et ainsi de suite. The condition need not be true in order for it to be a proposition. In fact, we might want to say that it is false or that it is true if some other proposition is true.

In this chapter, we first look at the syntactic rules that define the language of Propositional Logic. We then introduce the notion of a truth assignment and use it to define the meaning of Propositional Logic sentences. After that, we present a mechanical method for evaluating sentences for a given truth assignment, and we present a mechanical method for finding truth assignments that satisfy sentences. We conclude with some examples of Propositional Logic in formalizing Natural Language and Digital Circuits.

2.2 Syntax

In Propositional Logic, there are two types of sentences -- simple sentences and compound sentences. Simple sentences express simple facts about the world. Compound sentences express logical relationships between the simpler sentences of which they are composed.

Simple sentences in Propositional Logic are often called proposition constants or, sometimes, logical constants. In what follows, we write proposition constants as strings of letters, digits, and underscores ("_"), where the first character is a lower case letter. Par exemple, raining is a proposition constant, as are rAiNiNg, r32aining, et raining_or_snowing. Raining is not a proposition constant because it begins with an upper case character. 324567 fails because it begins with a number. raining-or-snowing fails because it contains hyphens (instead of underscores).

Compound sentences are formed from simpler sentences and express relationships among the constituent sentences. There are five types of compound sentences, viz. negations, conjunctions, disjunctions, implications, and biconditionals.

UNE negation consists of the negation operator ¬ and an arbitrary sentence, called the target. For example, given the sentence p, we can form the negation of p as shown below.

UNE conjunction is a sequence of sentences separated by occurrences of the &and operator and enclosed in parentheses, as shown below. The constituent sentences are called conjuncts. For example, we can form the conjunction of p et q as follows.

UNE disjunction is a sequence of sentences separated by occurrences of the &or operator and enclosed in parentheses. The constituent sentences are called disjuncts. For example, we can form the disjunction of p et q as follows.

Une implication consists of a pair of sentences separated by the &rArr operator and enclosed in parentheses. The sentence to the left of the operator is called the antecedent, and the sentence to the right is called the consequent. The implication of p et q is shown below.

UNE biconditional is a combination of an implication and a reverse implication. For example, we can express the biconditional of p et q as shown below.

Note that the constituent sentences within any compound sentence can be either simple sentences or compound sentences or a mixture of the two. For example, the following is a legal compound sentence.

One disadvantage of our notation, as written, is that the parentheses tend to build up and need to be matched correctly. It would be nice if we could dispense with parentheses, e.g. simplifying the preceding sentence to the one shown below.

Unfortunately, we cannot do without parentheses entirely, since then we would be unable to render certain sentences unambiguously. For example, the sentence shown above could have resulted from dropping parentheses from either of the following sentences.

The solution to this problem is the use of operator precedence. The following table gives a hierarchy of precedences for our operators. The ¬ operator has higher precedence than &and &and has higher precedence than &or &or has higher precedence than &rArr and &rArr has higher precedence than &hArr.

In sentences without parentheses, it is often the case that an expression is flanked by operators, one on either side. In interpreting such sentences, the question is whether the expression associates with the operator on its left or the one on its right. We can use precedence to make this determination. In particular, we agree that an operand in such a situation always associates with the operator of higher precedence. The following examples show how these rules work in various cases. The expressions on the right are the fully parenthesized versions of the expressions on the left.

¬ p &and q ((¬ p) &and q)
p &and ¬q (p &and (¬ q))
p &and q &or r ((p &and q) &or r)
p &or q &and r (p &or (q &and r))
p &rArr q &hArr r ((p &rArr q) &hArr r))
p &hArr q &rArr r (p &hArr (q &rArr r))

When an operand is surrounded by two &and operators or by two &or operators, the operand associates to the left. When an operand is surrounded by two &rArr operators or by two &hArr operators, the operand associates to the right.

p &and q &and r ((p &and q) &and r))
p &or q &or r ((p &or q) &or r))
p &rArr q &rArr r (p &rArr (q &rArr r))
p &hArr q &hArr r (p &hArr (q &hArr r))

Note that just because precedence allows us to delete parentheses in some cases does not mean that we can dispense with parentheses entirely. Consider the example shown earlier. Precedence eliminates the ambiguity by dictating that the sentence without parentheses is an implication with a disjunction as antecedent. However, this makes for a problem for those cases when we want to express a disjunction with an implication as a disjunct. In such cases, we must retain at least one pair of parentheses.

We end the section with two simple definitions that are useful in discussing Propositional Logic. UNE propositional vocabulary is a set of proposition constants. UNE propositional language is the set of all propositional sentences that can be formed from a propositional vocabulary.

2.3 Semantics

The treatment of semantics in Logic is similar to its treatment in Algebra. Algebra is unconcerned with the real-world significance of variables. What is interesting are the relationships among the values of the variables expressed in the equations we write. Algebraic methods are designed to respect these relationships, independent of what the variables represent.

In a similar way, Logic is unconcerned with the real world significance of proposition constants. What is interesting is the relationship among the truth values of simple sentences and the truth values of compound sentences within which the simple sentences are contained. As with Algebra, logical reasoning methods are independent of the significance of proposition constants all that matter is the form of sentences.

Although the values assigned to proposition constants are not crucial in the sense just described, in talking about Logic, it is sometimes useful to make truth assignments explicit and to consider various assignments or all assignments and so forth. Such an assignment is called a truth assignment.

Formally, a truth assignment for a propositional vocabulary is a function assigning a truth value to each of the proposition constants of the vocabulary. In what follows, we use the digit 1 as a synonym for vrai and 0 as a synonym for faux and we refer to the value of a constant or expression under a truth assignment je by superscripting the constant or expression with je as the superscript.

The assignment shown below is an example for the case of a propositional vocabulary with just three proposition constants, viz. p, q, et r.

p i = 1
q i = 0
r i = 1

The following assignment is another truth assignment for the same vocabulary.

p i = 0
q i = 0
r i = 1

Note that the formulas above are not themselves sentences in Propositional Logic. Propositional Logic does not allow superscripts and does not use the = symbol. Rather, these are informal, metalevel statements about particular truth assignments. Although talking about Propositional Logic using a notation similar to that Propositional Logic can sometimes be confusing, it allows us to convey meta-information precisely and efficiently. To minimize problems, in this book we use such meta-notation infrequently and only when there is little chance of confusion.

Looking at the preceding truth assignments, it is important to bear in mind that, as far as logic is concerned, any truth assignment is as good as any other. Logic itself does not fix the truth assignment of individual proposition constants.

On the other hand, donné a truth assignment for the proposition constants of a language, logic Est-ce que fix the truth assignment for all compound sentences in that language. In fact, it is possible to determine the truth value of a compound sentence by repeatedly applying the following rules.

If the truth value of a sentence is vrai, the truth value of its negation is faux. If the truth value of a sentence is faux, the truth value of its negation is vrai.

The truth value of a conjunction is vrai if and only if the truth values of its conjuncts are both vrai otherwise, the truth value is faux.

&phi &psi &phi &and &psi
1 1 1
1 0 0
0 1 0
0 0 0

The truth value of a disjunction is vrai if and only if the truth value of at least one its disjuncts is vrai otherwise, the truth value is faux. Note that this is the inclusive or interpretation of the &or operator and is differentiated from the exclusive or interpretation in which a disjunction is true if and only if an odd number of its disjuncts are true.

&phi &psi &phi &or &psi
1 1 1
1 0 1
0 1 1
0 0 0

The truth value of an implication is faux if and only if its antecedent is vrai and its consequent is faux otherwise, the truth value is vrai. This is called material implication.

&phi &psi &phi &rArr &psi
1 1 1
1 0 0
0 1 1
0 0 1

A biconditional is vrai if and only if the truth values of its constituents agree, i.e. they are either both vrai ou les deux faux.

&phi &psi &phi &hArr &psi
1 1 1
1 0 0
0 1 0
0 0 1

Using these definitions, it is easy to determine the truth values of compound sentences with proposition constants as constituents. As we shall see in the next section, we can determine the truth values of compound sentences with other compound sentences as parts by first evaluating the constituent sentences and then applying these definitions to the results.

We finish up this section with a few definitions for future use. We say that a truth assignment satisfies a sentence if and only if the sentence is vrai under that truth assignment. We say that a truth assignment falsifies a sentence if and only if the sentence is faux under that truth assignment. A truth assignment satisfies a set of sentences if and only if it satisfies tous sentence in the set. A truth assignment falsifies a set of sentences if and only if it falsifies at least one sentence in the set.

2.4 Evaluation

Evaluation is the process of determining the truth values of compound sentences given a truth assignment for the truth values of proposition constants.

As it turns out, there is a simple technique for evaluating complex sentences. We substitute true and false values for the proposition constants in our sentence, forming an expression with 1s and 0s and logical operators. We use our operator semantics to evaluate subexpressions with these truth values as arguments. We then repeat, working from the inside out, until we have a truth value for the sentence as a whole.

As an example, consider the truth assignment je shown below.

p i = 1
q i = 0
r i = 1

Using our evaluation method, we can see that je satisfies (p &or q) &and (¬q &or r).

Now consider truth assignment j defined as follows.

p j = 0
q j = 1
r j = 0

In this case, j does not satisfy (p &or q) &and (¬q &or r).

Using this technique, we can evaluate the truth of arbitrary sentences in our language. The cost is proportional to the size of the sentence. Of course, in some cases, it is possible to economize and do even better. For example, when evaluating a conjunction, if we discover that the first conjunct is false, then there is no need to evaluate the second conjunct since the sentence as a whole must be false.

2.5 Satisfaction

Satisfaction is the opposite of evaluation. We begin with one or more compound sentences and try to figure out which truth assignments satisfy those sentences. One nice feature of Propositional Logic is that there are effective procedures for finding truth assignments that satisfy Propositional Logic sentences. In this section, we look at a method based on truth tables.

UNE truth table for a propositional language is a table showing all of the possible truth assignments for the proposition constants in the language. The columns of the table correspond to the proposition constants of the language, and the rows correspond to different truth assignments for those constants.

The following figure shows a truth table for a propositional language with just three proposition constants (p, q, et r). Each column corresponds to one proposition constant, and each row corresponds to a single truth assignment. The truth assignments je et j defined in the preceding section correspond to the third and sixth rows of this table, respectively.

p q r
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0

Note that, for a propositional language with m proposition constants, there are m columns in the truth table and 2 m rows.

In solving satisfaction problems, we start with a truth table for the proposition constants of our language. We then process our sentences in turn, for each sentence placing an x next to rows in the truth table corresponding to truth assignments that do not satisfy the sentence. The truth assignments remaining at the end of this process are all possible truth assignments of the input sentences.

As an example, consider the sentence p &or q &rArr q &and r. We can find all truth assignments that satisfy this sentence by constructing a truth table for p, q, et r. Voir ci-dessous. We place an x next to each row that does not satisfy the sentence (rows 2, 3, 4, 6). Finally, we take the remaining rows (1, 5, 7, 8) as answers.

p q r
1 1 1
X 1 1 0 X
X 1 0 1 X
X 1 0 0 X
0 1 1
X 0 1 0 X
0 0 1
0 0 0

The disadvantage of the truth table method is computational complexity. As mentioned above, the size of a truth table for a language grows exponentially with the number of proposition constants in the language. When the number of constants is small, the method works well. When the number is large, the method becomes impractical. Even for moderate sized problems, it can be tedious. Even for an application like Sorority World, where there are only 16 proposition constants, there are 65,536 truth assignments.

Over the years, researchers have proposed ways to improve the performance of truth table checking. However, the best approach to dealing with large vocabularies is to use symbolic manipulation (i.e. logical reasoning and proofs) in place of truth table checking. We discuss these methods in Chapters 4 and 5.

2.6 Example - Natural Language

As an exercise in working with Propositional Logic, let's look at the encoding of various English sentences as formal sentences in Propositional Logic. As we shall see, the structure of English sentences, along with various key words, such as si et non, determine how such sentences should be translated.

The following examples concern three properties of people, and we assign a different proposition constant to each of these properties. We use the constant c to mean that a person is cool. We use the constant F to mean that a person is funny. And we use the constant p to mean that a person is popular.

As our first example, consider the English sentence If a person is cool or funny, then he is popular. Translating this sentence into the language of Propositional Logic is straightforward. The use of the words si et then suggests an implication. The condition (cool or funny) is clearly a disjunction, and the conclusion (popular) is just a simple fact. Using the vocabulary from the last paragraph, this leads to the Propositional Logic sentence shown below.

Next, we have the sentence A person is popular only if he is either cool or funny. This is similar to the previous sentence, but the presence of the phrase only if suggests that the conditionality goes the other way. It is equivalent to the sentence If a person is popular, then he is either cool or funny. And this sentence can be translated directly into Propositional Logic as shown below.

A person is popular if and only if he is either cool or funny. The use of the phrase si et seulement si suggests a biconditional, as in the translation shown below. Note that this is the equivalent to the conjunction of the two implications shown above. The biconditional captures this conjunction in a more compact form. p &hArr c &or F

Finally, we have a negative sentence. There is no one who is both cool and funny. Le mot non here suggests a negation. To make it easier to translate into Propositional Logic, we can first rephrase this as It is not the case that there is a person who is both cool and funny. This leads directly to the following encoding.

Note that, just because we can translate sentences into the language of Propositional Logic does not mean that they are true. The good news is that we can use our evaluation procedure to determine which sentences are true and which are false?

Suppose we were to imagine a person who is cool and funny and popular, i.e. the proposition constants c et F et p are all true. Which of our sentences are true and which are false.

Using the evaluation procedure described earlier, we can see that, for this person, the first sentence is true.

The second sentence is also true.

Since the third sentence is really just the conjunction of the first two sentences, it is also true, which we can confirm directly as shown below.

Unfortunately, the fourth sentence is not true, since the person in this case is both cool and funny.

In this particular case, three of the sentences are true, while one is false. The upshot of this is that there is no such person (assuming that the theory expressed in our sentences is correct). The good news is that there are cases where all four sentences are true, e.g. a person who is cool and popular but not funny or the case of a person who is funny and popular but not cool. Question to consider: What about a person is neither cool nor funny nor popular? Is this possible according to our theory? Which of the sentences would be true and which would be false?

2.7 Example - Digital Circuits

Now let's consider the use of Propositional Logic in modeling a portion of the physical world, in this case, a digital circuit like the ones used in building computers.

The diagram below is a pictorial representation of such a circuit. There are three input nodes, some internal nodes, and two output nodes. There are five gates connecting these nodes to each other - two xor gates (the gates on the top), two et gates (the gates on the lower left), and one or gate (the gate on the lower right).

At a given point in time, a node in a circuit can be either sur ou alors off. The input nodes are set from outside the circuit. A gate sets its output either sur ou alors off based on the type of gate and the values of its input nodes. The output of an et gate is sur if and only if both of its inputs are sur. The value of an ou alors node is sur if and only if at least one of its inputs is sur. The output of an xor gate is sur if and only if its inputs disagree with each other.

Given the Boolean nature of signals on nodes and the deterministic character of gates, it is quite natural to model digital circuits in Propositional Logic. We can represent each node of a circuit as a proposition constant, with the idea that the node is sur if and only if the constant is true. Using the language of Propositional Logic, we can capture the behavior of gates by writing sentences relating the values of the inputs nodes and out nodes of the gates.

The sentences shown below capture the five gates in the circuit shown above. Node o must be sur if and only if nodes p et q disagree.

(p &and ¬q) &or (¬p &and q) &hArr o
r &and o &hArr une
p &and q &hArr b
(o &and ¬r) &or (¬o &and r) &hArr s
une &or b &hArr c

Once we have done this, we can use our formalization to analyze the circuit - to determine if it meets it specification, to test whether a particular instance is operating correctly, and to diagnose the problem in cases here it is not.

Recap

The syntax of Propositional Logic begins with a set of proposition constants. Compound sentences are formed by combining simpler sentences with logical operators. In the version of Propositional Logic used here, there are five types of compound sentences - negations, conjunctions, disjunctions, implications, and biconditionals. UNE truth assignment for Propositional Logic is a mapping that assigns a truth value to each of the proposition constants in the language. A truth assignment satisfies a sentence if and only if the sentences is vrai under that truth assignment according to rules defining the logical operators of the language. Evaluation is the process of determining the truth values of a complex sentence, given a truth assignment for the truth values of proposition constants in that sentence. Satisfaction is the process of determining whether or not a sentence has a truth assignment that satisfies it.

Problems

Problem 2.1: Say whether each of the following expressions is a syntactically legal sentence of Propositional Logic.

(une)p &and ¬p
(b)¬p &or ¬p
(c)¬(q &or r) ¬q &rArr ¬¬p
()(p &and q) &or (p ¬&and q)
(e)p &or ¬q &and ¬p &or ¬q &rArr p &or q

Problem 2.2: Consider a truth assignment in which p is true, q is false, r is true. Use this truth assignment to evaluate the following sentences.

(une)p &rArr q &and r
(b)p &rArr q &or r
(c)p &and q &rArr r
()p &and q &rArr ¬r
(e)p &and q &hArr q &and r

Problem 2.3: A small company makes widgets in a variety of constituent materials (aluminum, copper, iron), colors (red, green, blue, grey), and finishes (matte, textured, coated). Although there are more than one thousand possible combinations of widget features, the company markets only a subset of the possible combinations. The following sentences are constraints that characterize the possibilities. Suppose that a customer places an order for a copper widget that is both green and blue with a matte coating. Your job is to determine which constraints are satisfied and which are violated.

(une)aluminium &or copper &or iron
(b)aluminium &rArr grey
(c)copper &and ¬coated &rArr red
()coated &and ¬copper &rArr green
(e)green &or blue &hArr ¬textured &and ¬iron

Problem 2.4: Consider the sentences shown below. There are three proposition constants here, meaning that there are eight possible truth assignments. How many of these assignments satisfy all of these sentences?

p &or q &or r
p &rArr q &and r
q &rArr ¬r

Problem 2.5: A small company makes widgets in a variety of constituent materials (aluminum, copper, iron), colors (red, green, blue, grey), and finishes (matte, textured, coated). Although there are more than one thousand possible combinations of widget features, the company markets only a subset of the possible combinations. The sentences below are some constraints that characterize the possibilities. Your job here is to select materials, colors, and finishes in such a way that tous of the product constraints are satisfied. Note that there are multiple ways this can be done.

aluminium &or copper &or iron
red &or green &or blue &or grey
aluminium &rArr grey
copper &and ¬coated &rArr red
iron &rArr coated

Problem 2.6: Consider a propositional language with three proposition constants - mushroom, purple, et poisonous - each indicating the property suggested by its spelling. Using these proposition constants, encode the following English sentences as Propositional Logic sentences.

(une)All purple mushrooms are poisonous.
(b)A mushroom is poisonous only if it is purple.
(c)A mushroom is not poisonous unless it is purple.
()No purple mushroom is poisonous.

Problem 2.7: Consider the digital circuit described in section 2.7. Suppose we set nodes p, q, et r to be sur, and we observe that all of the other nodes are sur. Running our evaluation procedure, we would see that the first sentence in our description of the circuit is not true. Hence the circuit is malfunctioning. Is there any combination of inputs p, q, et r that would result in all other nodes being sur in a correctly functioning circuit? Hint: To answer this, you need consider a truth table with just eight rows (the possible values for nodes p, q, et r) since all other nodes are observed to be sur.


Example: An island has two kinds of inhabitants, knights, who always tell the truth, and knaves,

who always lie. You go to the island and meet A and B. - A says “B is a knight.” - B says “The two of us are of opposite types.” What are the types are A and B?

Example: When three professors are seated in a restaurant, the hostess asks them: “Does everyone want coffee?” The first professor says: “I do not know.” The second professor says: “I do not know.” Finally, the third professor says: “No, not everyone wants coffee.” The hostess comes back and gives coffee to the professors who want it. How did she figure out who wants coffee?


Exercise: 2 stars, advanced (True)

Definition not ( P : Prop ) := P &rarr False .

Notation "¬ x" := ( not x ) : type_scope .

Theorem not_False :
¬ False .
Preuve .
unfold not . intros H . inversion H . Qed .

Theorem contradiction_implies_anything : &forall P Q : Prop ,
( P &and ¬ P ) &rarr Q .
Preuve .
(* WORKED IN CLASS *)
intros P Q H . inversion H as [ HP HNA ]. unfold not in HNA .
apply HNA in HP . inversion HP . Qed .

Theorem double_neg : &forall P : Prop ,
P &rarr

P .
Preuve .
(* WORKED IN CLASS *)
intros P H . unfold not . intros G . apply G . apply H . Qed .