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
3 answers

How to find the no of years in which population of both.the cities become equal?

City A' s population is $96000$ and it is decreasing by $800$ per year and city B' s population is $68000$ which is increasing by $1200$ per year. After how many years population of both the city becomes equal? If I have to solve this question in…
1
vote
2 answers

When is both a statement and its negation incorrect?

In Chiswell's Mathematical Logic, one of the exercises is to show that the following statement admits counterexamples: if $\Gamma\vdash(\phi\lor\psi)$ is a correct sequent then at least one of $\Gamma\vdash\phi$ and $\Gamma\vdash\psi$ is also…
Doubt
  • 1,719
1
vote
1 answer

Is $¬r→q = r \vee q$?

I know that by conversion theorem, $ r → q = \lnot r \vee q $. So if $¬r → q$ will be equal to $r \vee q$ and not $r \vee ¬q$ right? Let's say we know that $q$ and $p$ are true. Given that $ r → s; ¬r → q; p \vee r;$ are true. How do we know that…
BEX
  • 37
1
vote
1 answer

proving [${\phi,\phi\to\psi}⊢\neg(\phi\to\neg\psi)$)] only with axioms

Is it possible to show ${\phi,\phi\to\psi}⊢\neg(\phi\to\neg\psi)$ only with modus ponens,deduction theorem and these three axiom? A1: $\phi\to(\psi\to\phi)$ A2: $(\phi\to(\psi\to\pi))\to((\phi\to\psi)\to(\phi\to\pi))$ A3:…
1
vote
1 answer

Hypothetical syllogism fallacy

Earlier in the textbook I'm reading we proved the sequent: $$\{ (\phi \rightarrow \psi),(\psi \rightarrow \chi) \} \vdash (\phi \rightarrow \chi)$$ We are later given an alleged counterexample: $\phi$ is the statement 'I imply you are a donkey'…
Cdizzle
  • 581
1
vote
1 answer

Is there a technical name for the number of implications between propositions?

Given 2 True/False boolean propositions $\mathcal{P}_1\{x_1\}$ and $\mathcal{P}_2\{x_2\}$, where $x_i\in \{T,F\}$ there are 7 possible relations between $\mathcal{P}_1\{x_1\}$ and $\mathcal{P}_2\{x_2\} \\$ 0 implications: 1) $\mathcal{P}_1$ bears no…
Ben Crossley
  • 2,544
1
vote
2 answers

Equivalance proof of ((p → q) ∧ ¬q) → ¬p and ((p ∨ q) ∧ ¬p) → q

I am trying to prove if the above propositional formulas is a tautology using the logic laws. However, I am really stuck, I don't know where else to go. Here is what I've done for the former formula. ((p → q) ∧ ¬q) → ¬p ((¬p ∨ q) ∧ ¬q) → ¬p…
1
vote
0 answers

Puzzling statement about implication in Gries and Schneider

I'm reading A Logical Approach to Discrete Math by David Gries and Fred B. Schneider and I got all snagged up on an apparent contradiction on an elementary point. On page 35, they write: For example, consider the sentence "If you don't eat your…
Reb.Cabin
  • 1,695
1
vote
3 answers

Do $p \lor q$ and only $p$ contradict each other?

If a theorem says $x = p$ only, but an assumption gives us $x = p \lor q$. Can I say they contradict each other and thus the assumption is wrong?
bt203
  • 71
1
vote
1 answer

Negating Multiple Nested Quantifiers

I am trying to rewrite the following propositions so that the negation acts on directly. ¬∃ ∃ (, ) ∃ ¬∀ ∃ ∀ (, , , w) Told by my prof that: Whenever there is negation of a quantification, the negation is "pushed" through the quantifier to…
1
vote
1 answer

Boolean Functional completeness of 5 operator set in propositional logic

I am trying to prove that the set of five connectives: $$\{ ¬, ∧, ∨, →, ↔\}$$ Is adequate (functionally complete) for all possible Boolean functions in propositional logic (only). I.e. EVERY Boolean function can be generated from these 5…
Drex
  • 69
1
vote
1 answer

Statement from Enderton's A Mathematical Introduction to Logic, Section 1.3.

Section 1.3, A Parsing Algorithm, presents an algorithm that given a wff, will produce its "ancestral tree". That is, a tree whose root is the complete wff, each leave is a sentence symbol, and each other node is an application of a connective…
1
vote
1 answer

Have I expressed this proposition correctly?

Up until I started writing this question, I have been attempting to teach myself these discrete math concepts, but now I want clarification on a question. From the book: Suppose that the domain of $Q$(x, y, z) consists of triples x, y, z, where x =…
Leonardo
  • 988
1
vote
4 answers

Prove equivalence $((P \Rightarrow Q) \land (P \Rightarrow R)) \iff (P\Rightarrow(Q\land R))$

Prove equivalence $$((P \Rightarrow Q) \land (P \Rightarrow R)) \iff (P\Rightarrow(Q\land R))$$ What is the step by step for the equivalence of these equations. I can first break down the implications and use the distributive property, but then I…
1
vote
1 answer

Converting text to propositional logic and use the truth table to find the solution

I'm having trouble representing these questions in a propositional logic formula: Alice, Bob and Claire want to attend the CPS I lecture. The exercise groups are almost full, only group 1 and group 2 have places left. (a) If Alice joins group 1,…
Rao208
  • 11
  • 3