Mathematics - Discrete Mathematics - Propositions and Connectives

over 2 years ago (Edited)

Introduction

Hey it's a me again @drifter1!

Today we continue with Mathematics, and more specifically the branch of "Discrete Mathematics", in order to get into Propositions and Connectives.

So, without further ado, let's get straight into it!

Propositional Logic

Propositional Logic is a branch of Mathematical Logic dealing with the relationship between propositions. Propositions are basically mathematical statements or sentences, which are connected through logical operators, known as connectives.

Propositions

A proposition or statement is a declarative sentence, which is either true or false. Such a proposition is simple (or atomic) when it can't be divided into multiple propositions and compound (or molecular) when it is the result of combining together multiple propositions.

Simple propositions are commonly denoted by lower-case letters starting from p and known as propositional variables.

For example, "It is raining" is a valid propositional statement, as it can only be true or false. On the other hand, "What's the weather like today?" is not a valid proposition, as the answer to that question isn't in true - false format.

Tautology, Contradiction and Contingency

A proposition which is always true is known as a tautology, whilst a proposition which is always false is known as a contradiction. A proposition is contingent when it is neither a tautology nor a contradiction.

Connectives

There are five main logical connectives. Four of them are binary, because they connect two propositions, whilst the last one is unary, as it is applied to a single proposition.

The logical connectives are:

Conjunction (AND)
Disjunction (OR)
Implication or Conditional (IF - THEN)
Equivalence or Bi-Conditional (IF AND ONLY IF)
Negation (NOT)

Commonly used symbols for these connectives are: ∧, ∨, →, ↔ and ¬, respectively.

Conjunction (AND)

A conjunction is a compound statement which is only true when all parts are also true. Otherwise, the result is false.

Disjunction (OR)

A disjunction is a compound statement which is true when at least one of the parts is true. So, it is only false when all parts of it are false.

Implication

An implication is a compound statement of the form p → q, where p is the hypothesis and q the conclusion. So, the implication is only false when p is true and q is false. Otherwise, it is true.

Equivalence

A bi-conditional compound statement is true only when both parts have the same logic value. Both true or both false.

Negation (NOT)

A negation is a statement with the opposite truth value than the original.

Derived Connectives

It is possible to derive some more connectives by combining the main connectives, these are:

NAND : which is conjunction followed by negation (only false when both are true)
NOR : which is disjunction followed by negation (only true when both are false)
XOR (Exclusive-OR) : which is true only when either proposition is true, not both at the same time (the commonly used symbol is ⊕)

RESOURCES:

References

Images

https://en.wikipedia.org/wiki/File:Modus_ponens_logical_form.jpg

Mathematical equations used in this article, have been generated using quicklatex.

Block diagrams and other visualizations were made using draw.io.

Previous articles of the series

Introduction → Discrete Mathematics, Why Discrete Math, Series Outline
Sets → Set Theory, Sets (Representation, Common Notations, Cardinality, Types)
Set Operations → Venn Diagrams, Set Operations, Properties and Laws
Sets and Relations → Cartesian Product of Sets, Relation and Function Terminology (Domain, Co-Domain and Range, Types and Properties)
Relation Closures → Relation Closures (Reflexive, Symmetric, Transitive), Full-On Example
Equivalence Relations → Equivalence Relations (Properties, Equivalent Elements, Equivalence Classes, Partitions)
Partial Order Relations and Sets → Partial Order Relations, POSET (Elements, Max-Min, Upper-Lower Bounds), Hasse Diagrams, Total Order Relations, Lattices
Combinatorial Principles → Combinatorics, Basic Counting Principles (Additive, Multiplicative), Inclusion-Exclusion Principle (PIE)
Combinations and Permutations → Factorial, Binomial Coefficient, Combination and Permutation (with / out repetition)
Combinatorics Topics → Pigeonhole Principle, Pascal's Triangle and Binomial Theorem, Counting Derangements