Languages

• Alphabet ($\Sigma$): A finite, non-empty set of symbols.
  • Example: $\Sigma = \{a, b\}$
• Word: A finite string of symbols from an alphabet.
• Empty Word ($\epsilon$): The unique word with zero symbols.
• Empty Set ($\emptyset$): The set with no elements.
• $\Sigma^*$: The set of all possible words that can be formed from the alphabet $\Sigma$, including the empty word $\epsilon$.

Key Language Examples

• EVEN-EVEN: The language where each string has an even number of 'a's and an even number of 'b's.
  • Note: Since 0 is an even number, the empty word $\epsilon$ is in EVEN-EVEN.
• DOUBLEWORD: The language of words formed by concatenating some word $w$ with itself.
  • Formally: $\{ww \mid w \in \Sigma^*\}$.
  • Note: $\epsilon = \epsilon\epsilon$, so $\epsilon$ is a doubleword.
• PALINDROMES: The language of words that read the same forwards and backwards.
  • Formally: $\{w \mid w = w^R\}$, where $w^R$ is the reverse of $w$.
• ODD-ODD: The language where each string has an odd number of 'a's and an odd number of 'b's.
  • Example: The word "a" is not in ODD-ODD. It has 1 'a' (odd) but 0 'b's (even). The word "abb" is also not in ODD-ODD (1 'a', 2 'b's). The word "ab" is in ODD-ODD.

Definitions, theorems, and proofs

Theorem: DOUBLEWORD ⊆ EVEN-EVEN (Every doubleword is also an even-even word).

Proof: Let $w$ be any word in $\Sigma^*$. Let the number of 'a's in $w$ be $n_a$ and the number of 'b's be $n_b$. The corresponding word in DOUBLEWORD is $ww$. The number of 'a's in $ww$ is $2n_a$ and the number of 'b's is $2n_b$. By definition, $2n_a$ and $2n_b$ are always even numbers. Therefore, any word in DOUBLEWORD is also in EVEN-EVEN.

Normal Forms

• Literal: A propositional variable or its negation (e.g., $A$ or $\neg A$).
• Disjunctive Normal Form (DNF): A disjunction (OR) of one or more clauses, where each clause is a conjunction (AND) of literals.
  • Structure: $(A \land \neg B) \lor (C \land D) \lor \dots$
• Conjunctive Normal Form (CNF): A conjunction (AND) of one or more clauses, where each clause is a disjunction (OR) of literals.
  • Structure: $(A \lor \neg B) \land (C \lor D) \land \dots$

Statements with variables

The variables in the statement are free, which means they have not been assign any values.

Predicates definitions and terminology

• Predicate: A statement with variables that becomes a proposition once the variables are given specific values from a domain. A predicate is called l-ary if it has k arguments.
  • Example: $P(x) = "x > 10"$. $P(12)$ is True, $P(5)$ is False.
• Universal Quantifier ($\forall$): Means "for all". $\forall x, P(x)$ asserts that $P(x)$ is true for every $x$ in the domain.
• Existential Quantifier ($\exists$): Means "there exists". $\exists x, P(x)$ asserts that there is at least one $x$ in the domain for which $P(x)$ is true.

Propositions and logical operations

• Proposition: A declarative sentence that is definitively True or False, but not both.
  • Paradox: "This statement is false" is a paradox, not a proposition, because its truth value cannot be determined without contradiction.
• Tautology: A statement that is always true, no matter the truth values of its variables (e.g., $p \lor \neg p$).
• Logical Equivalence ($\equiv$): Two statements are logically equivalent if they always have the same truth value.
  • Example: De Morgan's Law states $\neg(p \land q) \equiv (\neg p \lor \neg q)$.

Changelog

8/8/25, 4:17 AM

View All Changelog

• 2aa48-web-deploy(Auto): Update base URL for web-pages branchon 8/8/25

Copyright

Copyright Ownership:WARREN Y.F. LONG

License under:Attribution-NonCommercial-NoDerivatives 4.0 International (CC-BY-NC-ND-4.0)