Questions tagged [propositional-calculus]

Appropriate for questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions. Also for general questions about the propositional calculus itself, including its semantics and proof theory. Questions about other kinds of logic should use a different tag, such as (logic), (predicate-logic), or (first-order-logic).

Propositional logic is a branch of logic dealing with logical connectives and statements involving them. A logical connective connects finitely many sentences and forms a compound sentence, in a way that the truth value of the compound sentence depends only on the truth value of its constituents. The most common connectives are the binary connectives conjunction ($\land$), disjunction ($\lor$) and implication ($\rightarrow$), the unary connective negation ($\neg$), and the nullary connectives true ($\top$) and false ($\bot$).

Any proposition is considered to be either atomic (in which case it has no constituents) or compound (in which case it's formed by mean a connective using simpler propositions). A propositional model is a function assigning to each atomic proposition a truth value $0$ or $1$. The truth values of compound propositions are then determined by the truth values of their constituents. For example, if $I$ is a function assigning truth values to propositions, one would have $I(\top)=1$, $I(\bot)=0$, $I(\neg A)=1-I(A)$, $I(A\land B)=\min\big(I(A),I(B)\big)$, $I(A\lor B)=\max\big(I(A),I(B)\big)$ and $I(A\rightarrow B)=\max\big(1-I(A),I(B)\big)$. The propositions having the value $1$ for every model, are called tautologies, and those having the value $0$ for every model, are called absurdities. A central task of propositional logic is characterizing tautologies and absurdities.

5541 questions
1
vote
2 answers

Bi conditional Statements:Did the author make a mistake in the passage?

The book I am reading called How to prove it mentions the following, which I think it might be wrong but not sure. One of the reasons it's so easy to confuse a conditional statement with its converse is that in everday speech we sometimes use a …
user93971
1
vote
1 answer

Translating propositional formulas

I've been given statements to translate into a propositional formula. The question states that it may also be possible for a statement to have multiple interpretations. I've having trouble determining whether or not this is the case for the…
Lex8erna
  • 113
1
vote
2 answers

If $\theta$ is a WFF, then $((\theta))$ is not a WFF

I can show that if $\theta$ is a WFF, then $(\theta)$ is not a WFF. Suppose $ (\theta )$ is a WFF. Then by unique readability, we know $(\theta) \equiv \neg\alpha$ or $(\theta) \equiv (\alpha \square \beta)$ for some formulae $\alpha$ and $\beta$…
Porky
  • 755
1
vote
1 answer

What is the minimal complexity formula equivalent to biconditional?

Suppose we are working in the propositional language whose only primitive logical connectives are $\rightarrow$ and $\neg$, standing for conditional and negation, respectively. Disjunction can be defined as $\neg A \rightarrow B$, conjunction can be…
user107952
  • 20,508
1
vote
2 answers

Inconsistency of propositional calculus given $(\neg A \to B) \to (A \to \neg B)$

Consider the classical propositional calculus system (Hilbert system) with three axiom shemes: (1) $A \to (B \to A)$, (2) $(A \to (B \to C)) \to ((A \to B) \to (A \to C))$, (3) $(\neg A \to \neg B) \to (B \to A)$. And you can use modus ponens. Now…
1
vote
2 answers

How do we prove that $p\wedge\neg p$ is a fallacy?

In my homework I was given this question: Prove that $p \land\lnot p$ is a fallacy. All I knew is that to prove a question like this you must have, two premises and a conclusion (For example: Prove that $p ∧ ¬Q, P Ⱶ ¬p$ is a fallacy or valid.…
1
vote
1 answer

The tableaux method for propositional calculus

I have recently been reading Raymond Smullyan's wonderful book titled Logical Labyrinths. I'm having trouble understanding the completeness proof of the Tableaux method for Propositional Calculus. In order to show that a sentence $X$ is a tautology,…
1
vote
0 answers

What are some examples of propositional logics which are not functionally complete?

In particular I'm interested in propositional logics with semantics given by truth tables which are not functionally complete, but which can define all their constant truth functions. I think the restriction of Post's lattice to clones containing…
jdonland
  • 197
1
vote
0 answers

"Syntactic" proof that disjunction of UNSAT formulas is UNSAT

Thanks a lot already in advance for any help! In short, I am in need somewhat like a syntactic proof that the disjunction of two unsatisfiable propositional formulas is unsatisfiable. More precisely, assume that we given a propositional formula…
Mens
  • 43
1
vote
3 answers

Proving statements like $(a\Rightarrow b) \Rightarrow (p \Rightarrow q)$.

Is there a way to simplify this sort of statement? For example, $$a \Rightarrow (b\Rightarrow c)$$ is equivalent to $$(a \wedge b) \Rightarrow c.$$ I'm looking for something similar for $$(a\Rightarrow b) \Rightarrow (p \Rightarrow q),$$ if it's…
Spine Feast
  • 4,770
1
vote
1 answer

Can conditional statements have unquantified variables in the hypothesis or conclusion?

How do quantified/unquantified variables work when considering conditional statements? The conditional is a statement, but the variables in the individual hypothesis/conclusion don't have to be quantified? i.e., can the hypothesis/conclusion be…
1
vote
1 answer

Using induction to prove an iff statement?

I am working on this problem on Enderton's book: 1.2.11. Show that a truth assignment $v$ satisfies the wff (...($A_1$ $\leftrightarrow$ $A_2$)$\leftrightarrow$ ... $\leftrightarrow$ $A_n$) iff $v(A_i)$ = $F$ for an even number of $i$'s, 1 $\leq$…
1
vote
1 answer

Propositional Logic: Confused on using operators with equal precedence

My problem involves using operators of equal precedence in propositional logic. I'm trying to use truth tables to prove the following: p ⇔ q ⇔ (p ⇒ q) ∧ (q ⇒ p) My problem however stems from the fact that I can see 2 ways to go about this. One…
Zsargul
  • 141
1
vote
1 answer

Propositional logic simplification using laws

I've been given the propisition below and the task to simplify it to the simplest equal proposition. $$ (p \rightarrow (q \vee r)) \rightarrow (p \wedge (q \vee r)) $$ I've been trying to do this for a bit now and the only steps I can possibly think…
1
vote
3 answers

Proving NOR is logically complete confusion

In this question I am very confused in part iii: Consider the connective ↓ (called the Pierce arrow or NOR), and defined by the truth-table below: P Q P ↓ Q 1 1 0 1 0 0 0 1 0 0 0 1 As you can see, the formula P ↓ Q is true when both P and Q are…