Elements of Logic

Elements of Logic

• Statements in common language and mathematics consist of propositions.
• Propositions are phrases with a clear true (1) or false (0) value.
• Capital letters A, B, and C denote generic propositions.
• The proposition A:{4 is an even number} is true.
• The proposition B:{7 is an even number} is false.
• The truth of proposition C:{x is an even number} can't be established without assigning a precise value to x; C is a propositional form.
• More complex statements take the logical form of composite propositions.
• Combine propositions according to precise rules containing single statements.
• Use logical connectives to create composite propositions.

Logical Connectives

• Negation symbol: not (¬); represents "not A".
• Conjunction symbol: e (∧); represents "A and B".
• Disjunction symbol: o (∨); represents "A or B".
• Implication symbol: ⇒; represents "A implies B". Double implication symbol: ⇔; represents "A if and only if B".
• Each connective operates as a logical operation.
• It associates new propositions with one or more propositions and uses parentheses like algebraic expressions to show the order of priority in compound proposition readings.
• The proposition [A ⇒ B e C] is ambiguous.
• It could mean [(A ⇒ B) e C] or [A ⇒ (B e C)].
• The latter is used in the absence of parentheses due to the order of priority assigned to the connectives.

Truth Tables

• Let A and B be generic propositions that can be either true or false.
• Assess the truth or falsehood of propositions made by several connectives.
• Proposition (not A) is false when A is true, and true when A is false.
• Proposition (A e B) is true when A and B are both true.
• It is false otherwise when A is false, B is false, or both are false.
• Proposition (A o B) is true when at least one of A or B is true.
• When A is true, B is true, or both are true; it is false when A and B are both false.
• Proposition (A ⇒ B) is true when A and B are both true, or when A is false.
• The value of truth of B is irrelevant; it is false when A is true and B is false.
• Proposition (A ⇔ B) is true when A and B have the same truth value.
• When both are true or both are false; it is false when A is true and B is false, or when A is false and B is true.
• The following truth tables summarize these connectives' outputs, with 2² = 4 possible truth/falsehood combinations for A and B.

Conditionality

• When the proposition A ⇒ B is true, A is a sufficient condition for B.
• B is a necessary condition for A.
• When the proposition A ⇔ B is true, A is a necessary and sufficient condition for B.
• A and B are logically equivalent propositions.
• Some logically equivalent propositions: A ⇒ B with (non A o B), and A ⇔ B with [(A ⇒ B) e (B ⇒ A)].

Tautologies

• Tautologies are propositions that are always true.
• Simple examples of tautologies include: (A o not A), [not (A e non A)], A ⇒ A, A ⇔ A, and A ⇔ non (non A).
• Other significant tautologies include: [not (A e B)] ⇔ (not A o not B) (De Morgan's I law), [not (A o B)] ⇔ (not A e not B) (De Morgan's II law), (A ⇒ B) ⇔ (non A o B), (A ⇔ B) ⇔ ((A ⇒ B) e (B ⇒ A)), [A e (B o non B)] ⇔ A, [Ao (B e non B)] ⇔ A, [non (A ⇒ B)] ⇔ (A e non B), (A ⇒ B) ⇔ (non B ⇒ non A) (Contraposition Principle), (A e (A ⇒ B)) ⇒ B (Modus Ponens), (non B e (A ⇒ B)) ⇒ non A (Modus Tollens).

Assessing Truth Values with Compiled Tables

• The data proposition is true when proposition A is false, independent of the value of the truth of proposition B.
• Equivalence logies allows of writing truth tables of equivalent to that data: [(A ⇒ B) e (B ⇒ non A)] → [(non A o B) e (non B o non A)], [(non A o B) e (non B o non A)] → [non (A e non B) e non (A e B)], [non (A e non B) e non (A e B)] ⇔ non [(A e non B) o (Ae B)].
• However, deduce ( or check with the tables) that: [(A ⇒ B) e (B ⇒ non A)] ⇔ non A.

Universaland Existential Quantifiers

• Symbols ∀ and ∃ are the universal ("for all") and existential ("there exists") quantifiers.
• ∀x: P(x) means "for every x, P(x) is true" or "for any x, P(x) is true".
• ∃x: P(x) means "there exists at least one x for which P(x) is true”.
• The proposition A:{∀x:x² > 0} reads: for any number x, its square is strictly greater than 0; this is a false proposition because 0² = 0.
• The proposition A: {∃x:x² > 0} reads: there exists at least one x whose square is strictly greater than 0; this is clearly a true proposition.
• The proposition A:{∀n ∈N : 2n is an even number} is true because the number 2n is even for any natural number n.
• The proposition B : {∃n∈N : n² < 0} is false because every natural number has a non-negative square.
• Sometimes the symbol ∃! is used, which instead reads as "there exists one and only...".
• The proposition A:{∃!x:x² = 0} reads: there exists one and only one x whose square is equal to 0; this proposition is true because only 0² = 0.
• If a proposition contains a quantifier, its negation is carried out using the other quantifier: if A : {∀x : P(x)}, then: not {∀x : P(x)} ⇔ {∃x : non P(x)}, while if A : {∃x : P(x)}, then: not {∃x : P(x)} ⇔ {∀x : non P(x)}.

Quantifier Examples

• This is a true proposition because 0² = 0.
• This is a false proposition in as much as only 0² = 0.

Sets: Basic Concepts

• The concept of a set is considered primitive, based on common experience.
• A set is made up of its elements.
• A set is given when its elements are known, that is, the elements that belong to it.
• A generic set is denoted by a capital letter, for example A, and the generic element by a.
• a∈ A (or А∋а) is written to indicate that the element a belongs to the set A.
• a ≠ A is written to indicate that the element a does not belong to the set A.
• A set can be given by describing its elements in detail, for example: A = {a,b,c,d} or also A = {1, 2, 3, ..., n, ...}.
• or by means of a property P(x) which its elements satisfy, writing: A = {x : P(x)}, for example: A = {x : x is an even number} or B = {x : x is Italian}.
• Note that writing {a,b,c,d} or {b,d,c, a} means the same set; therefore, the order of enumeration of the elements does not count to describe a set.
• Finally, a writing of the type A = {a, a, b, c} makes no sense; i.e., one and the same element a cannot belong to the set more than once.

Subsets and Inclusion

• Given two sets any A and B, give a relationship.
• A is contained in B, or A is a subset of B, and ACB is written (every element of A also belongs to B): (ACB) ⇔ (x ∈ A ⇒ x ∈ B) .
• Formally define the equality between two sets A and B as follows: (A = B) ⇔ ((ACB)e(BCA)).
• The writing ACB means that A is contained in B, also allowing for the two sets to coincide.
• Let Ø be called an empty set and is an element-free set, avremo che Ø CA, VA.
• B. Russell has demonstrated that a set that contains every other set cannot exist, that is, a universal set to which everything belongs.
• When necessary, we can, however, fix a universal set (relative), suitably chosen, to appropriately limit the scope of the problem.
• Let's denote this universal set with U; naturally, it follows that ACU, VA.

Set Parts

• Having a set A, a set of parts of A is defined, and is indicated by P(A).
• P(A) = {B : B ⊆ A}, that is, the set with all the possible subsets of A as its elements.
• Since Ø CA e che A ⊆ A, it follows that Ø ∈ P(A) e A∈P(A), VA.
• Example: Be A = {1,2,3}.
• In that case it's clear that: P(A) = {0, 1}, {2}, {3}, {1, 2}, {1,3}, {2, 3}, {1, 2, 3}}.

Set Operations

• Having a set A and given a set (universal) U, there is the:
• Definition: Complementary of A (with respect to U), is indicated with C(A) (or with A’).
• The l'insieme: C(A) = {x : x ∉ A}, that is, the set made up of the elements of U that do not belong to A.
• Example: Let A = {1,2,3} e U = {1, 2, 3, 4, 5}.
• In that case C(A) = {4,5}.
• If it were U = {1, 2, 3, 4, 5, 6, 7}, C(A) = {4, 5, 6, 7}.
• Set operations operate on at least two sets

Intersection and Partition

• Definition: given two sets A and B, an intersection is given by A∩B, and the l'insieme: A ∩ B = {x: x ∈ A e x ∈ B} = {x: x ∈ A e x ∈ B}, i.e., the set consisting of the elements that belong to both A and B.
• Example: Let A = {1,2,3} and B = {1,2,4,5} and B = {1,2,4,5} ; in that case A∩B = {1,2}. If instead A = {1,2,4,5} e B = {4,5}, then A ∩ B = 0.
• With intersection of a generic number of sets: A1, A2, ..., An .
• An element x ∈ intersection of A₁ if x belongs to each of the A₁.
• Definition: Given two sets A and B, a union is indicated by AUB.
• The l'insieme: A ∪ B = {x :x ∈ A o x ∈ B} which means the set consisting of the elements that belong to A or belong to B, or both.
• Example: Let A = {1,2,3} and B = {1,2,4,5}. Then AUB = {1,2,3, 4, 5} .
• As can be seen, the elements 1 and 2, which belong both to A and to B, appear only once in AUB.
• With UA is indicated the union of a generic number n of sets : A1, A2, ..., An .
• An element x ∈ union of A₁ if x belongs to at least one of the Aż.
• Definition: Given a set A, we say that n of its subsets Aż constitute a set partitioning of A if:
• I) unionA = A
• II) A¡ ∩ Aj = 0, for i ≠ j.

Difference and Symmetric Difference

• Definition: Given two sets A and B, the difference is indicated with A \ B.
• A \ B = {x :x ∈ A ex ∉ B, also means to express the set consisting of the elements of A that do not belong to B.
• Example: Siano A = {1,2,3} and B = {1,2,4,5}; in that case, the A \ B = {3}, while instead B \ A = {4,5} .
• Take note of how the sets A∩B, A\B and B \ A constitute a partition of AUB.
• They have to have elements in comune and in addition: AUB = (A∩B) U (A \ B) U (B \ A) .
• Definition: Given two sets A and B, the symmetric difference is given by A△B.
• A △ B = {x : (x ∈ A e x ∉ B) o (x ∉ A e x ∈B)}, means to express the set consisting of the elements of A that do not belong to B and of the elements of B that do not belong to A.
• A △ B = (A \ B) U (B \ A) = (AUB) (A∩B).
• Membership Tables help to illustrate these relationships

Set Operation Analogies

• Note the analogies between the truth tables of the logical connectives.
• Non, and, o, e those of the set operations (complementary, intersection and union) are defined by them.
• Verify valid relations via the membership tables.

Properties of Intersertion and Union

• Various set operations exhibit commutativity, associativity, and distributivity.
• De Morgan's laws are also described

Cartesian Product of Sets

• Given two sets A and B, a Cartesian product is indicated by A × B.
• It is the set: A × B = {(a, b) : a ∈ A,b∈B}.
• The Cartesian product A × B is the set consisting of all the possible pairs having as the first element any element of A and as the second element any element of B.
• The pair (a, b) constitutes an element whose nature is different both from that of a and from that of b.
• There is no operation to be carried out between a and b in the pair (a, b).
• The defintion in all cases, says has the A × B ≠ B × A, e che A × 0 = 0.

Cartesian Products Examples

• An example: let A = {1,2,3} and B = {a,b}.
• Then we will have A × B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)} .
• Instead B × A = {(a, 1), (b, 1), (a, 2), (b, 2), (a, 3), (b, 3)} .
• An example: Let A = {1, - 1} e B = {1, – 1} .
• Then we will have A × B = {(1, 1), (1, — 1), ( – 1, 1), ( − 1, − 1)} = B × A.
• Analogously, given n sets A₁, 1 ≤ i ≤ n, we define their Cartesian product as: A1 × A2 × ... × An = {(a1, a2, ..., an) : ai ∈ Ai, 1 ≤ i ≤ n}
• The set consisting of all the possible n-uple with an element of the i-esimo set A₁ as the i-esimo element instead.
• In the case it were A₁ = A, Vi : 1 ≤ i ≤ n, we will also write A×A× ... × A = An .

Relations

• Given two sets X and Y, a relation R from X in Y, R : X → Y, is said to be any subset of their Cartesian product: R ≤ X ×Y.
• A past definition of relation consisted in asking that some element of X was linked (or in relation) with some element of Y.
• The given definition, instead, also includes the empty relation, R = 0, and the total relation R = X × Y.
• A relation is hence described by a set of ordered pairs (x, y), with x ∈Xey∈Y.
• Then we will write (x, y) ∈ R, or also xRy, to say that x is in relation with y.

Relations and Properties

• Relations in a set are self-contained. It represents a case of particular interest.

• Let X then be a set and be R a relation from X in X; the relation R is said to be:

• reflexive if ∀x:xRx (every element is in relation with itself);

• symmetric if (x1Rx2) ⇒ (x2Rx1) (if an element is in relation with one, then the latter is also in relation with the former);

• antisimmetric if ((x1Rx2) e (x2Rx1)) ⇒ (x1 = x2) (if a pair satisfies to symmetry property, in the latter it regards reflexivity);

• transitive if ((x1Rx2) e (x2Rx3)) ⇒ (x1Rx3) (if an element is in relation with the latter, and the latter is in relation with a third element, also the first element and the there are in relation);

• full if ∀x1, x2 : (x1Rx2) 0 (x2Rx1) 0 (x1 = x2) (for every pair of elements, the first is in relation with the latter, or it that the latter is in retion with the first, or the two elements are the same element).

Additional Definitions

• These more properties are also defined and are the following:
• irreflexive if ∀x : non (xRx) (no element is in relation with itself);
• areflexive if (∃x₁ ∈ X : x₁Rx1) e (∃x2 ∈ X : non (x2Rx2)) (some element is in relation with itself and another element is not);
• asymmetric if (x1Rx2) ⇒ (non (x2Rx1)) (if an element is in relation with a second element, then this is not in relations with the first);
• negatively transitive if (non (x1Rx2)) e (non (x2Rx3)) ⇒ non (x1Rx3) (if an element is not in relation with a the latter and the latter is not in relation with a third, the first and third elements are not in relation).

Equivalence

• Let X be a set and R a relation from X in X; R is called equivalence relation it is satisfies to the following properties: I) reflexive, II) symmetric, III) transitive.

Class Types

• Let R be a relation of equivalence in X, and be x₁ ∈ X.
• Is said "equivalence class" of x1, and is indicated with [x1], the set made up of by the elements x ∈ X which are in relation with (or are equivalent to) x1 : [x1] = {x ∈ X : xRx1}.
• From the definition of relation of equivalence the following is deduced: I) every x ∈ X belongs to one single class of equivalence; II) distinct classes of equivalence do not have elements in common.

Further Definition and Examples

• Let X be a set and R the equivalence relation defined in X.
• Then set "quotient" of X with respect to the relation of equivalence R is called, and is indicated then simbol X/R , is "l'insieme costituito dalle classi di equivalenza originate dalla relazione ℛ"
• that is, X /~ = {[x] : x ∈ X} .
• We know In the Properties set we described it, of 19 properties , L'insieme quoziente, viste le proprietà I) e II), costituisce una partizione di X, ovvero:
• I) ∪ [xi] = X.
• II) [xi] ∩ [xj] = Ø, se i ≠ j.

Order of Relations

• Let X be a set and R a relation from X in X.
• R is said to be a preordering relation if it satisfies the following properties:
• I) reflexive, II) transitive.
• Let X be a set and R a relation from X in X, R is said to be an order relation if it satisfies the following properties:
• I) reflexive, II) antisimmetric, III) transitive.
• An order relation is said to be a complete relationship and includes a whole relation, otherwise it is called partial.
• Some authors introduce other types of order relation, defined by its properties:

Further Relations

Types that are defined by properties:

• relation of preordering weakly: I) reflexive II) transitive
• relation of preordering strict: I) irreflexive II) transitive III) transitive
• relation of order weakly
• I) reflexive II) antisimmetric III) transitive
• relation of order strict
• I) assimetric II) negatively transitive In this classification the relations of order weakly they coincides with that that previously we called relations of order. Let X be a set and R a relation of order defined in X.
• If x Ry; we will say also than x pre - established and we will write x < y to the place of x Ry.*

Limitated terms

Here's some things to think about regarding Limitated and unloimitate sets where U is the universe chosen:

• AUA=A;
• AUØ = A;
• AUU=U;
• ANA=A:
• An0 = 0
• ANU=A
• commutate proprietà
• AUB=BUA; ANB=BNA:
• proprietà di assorbimento
• AU(A∩B)=A ;AN(AUB)=A
• Associutive proprietà
• AU(BUC)=(AUB)UC ;AN(B∩C)=(A∩B)∩C
• distributuive proprietà
• AU(BNC)=(AUB)∩(AUC) ; AN(BUC) =(A∩B) U(A ∩C)
• De Morgan laws
• C(A U B) = C(A) ∩C(B) ; C(A∩ B)= C(A) UC(B)

Max, Min & Minor Terms Described

• Sia X è un insieme e R è una relazione di ordine in X Valgono the sequenziali Definition :" The elemento M ∈ X can be considerd to be alwas at its Max se: " ∀x ∈ X, M ≥ x";

Definition **:"**The elemento m ∈ X to considere this a minore to the "se: ∀x ∈ X, m ≤ x ". Also notic how this two define are also need to "the part of "al'inserimento alal'insieme

   But in conclusion if ever a  elemento It’s at "il Massimo"minimo" alora è anche the Massimo"minimo

• *"**if R order relation is in X, UN elemento resulting this "Massimo"minimo) will"also be "Massimo"minimo per relazio
• Per la relation that in the point 20, is is the element R dell'Esempio 20 in X₁ = {1,2,3,4,5,6.
• Per that relation .

Other Terms

• Un caso "uno specifico" di relazione of "è to the fine the funzio "funzioni",diamon the se" and definition from function