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
2
votes
1 answer

Proving statements of the form $Q(X)$ or $R(X) \implies P(X)$

I am currently trying to prove a statement that has the following form: $(Q(X)$ or $R(X)) \implies P(X)$. I usually start by taking $Q(X)$ or $R(X)$ as hypothesis; this means that $Q(X)$ is the case, or that $R(X)$ is the case, or that both are the…
Alistair -L.
  • 163
  • 4
2
votes
1 answer

How does one get rid of $ p $?

How does one get rid of $ p $ in $(p\Leftrightarrow q) \wedge (p\Leftrightarrow r) $? I have already tried to simplify the formula, applied DeMorgan's laws, etc, but nothing helps. Does anyone know how to deal with this?
Constantine
  • 1,429
2
votes
1 answer

If $P \implies Q \implies R$ holds, does it follow that $\lnot R \implies \lnot Q \implies \lnot P$ is also true?

I know that implications are not associative. So I guess my question is: What interpretation for $$P \implies Q \implies R$$ should I use, so that $$\left(P \implies Q \implies R\right) \equiv \left(\lnot R \implies \lnot Q \implies \lnot…
2
votes
0 answers

Counting elements with propositions

I recently had a test which asked various things about propositional logic: natural deduction, truth table's, analytic tableau's, ... The very first question asked to create a truth table of φ and then give the amount of "elements" in Σ. Given: Σ =…
2
votes
0 answers

Calculus of indications: Why does $\overline{a \; b |}$ gives us the connective for the Sheffer stroke?

I'm reading Williams "Logic and Integer Programming", here: Question: I think I understand why $\overline{a |}$ gives the truth table given in there but why does $\overline{a \; b |}$ gives us the connective for the Sheffer stroke?
Red Banana
  • 23,956
  • 20
  • 91
  • 192
2
votes
1 answer

Some basic questions about propositional logic prompted by a multiple choice question in Digital Fundamentals

I'm not sure how to think about the relationship between the statements any input is LOW; no inputs are HIGH; and the output of an AND gate is LOW. The context is my textbook, the 11th edition of Digital Fundamentals by Thomas Floyd, which…
2
votes
3 answers

From $A⇒B$ and $B⇒C$ can we conclude $C$?

Is the following valid: Premises: If Bob eats breakfast, he won't eat lunch. If Bob doesn't eat lunch he will have an early dinner Conclusion: Bob will have an early dinner I think this is valid. The premises are in the form $A ⇒ B, B ⇒ C$. They…
ENV
  • 728
2
votes
1 answer

I can't seem to prove that (p ∨ q) ∧ (¬p ∨ r) → (q ∨ r) is a tautology.

Here are my steps: (p ∨ q) ∧ (¬p ∨ r) → (q ∨ r) ¬[ (p ∨ q) ∧ (¬p ∨ r) ] ∨ (q ∨ r) implication to disjunction ¬(p ∨ q) ∨ ¬(¬p ∨ r) ∨ (q ∨ r) demorgans law (¬p ∧ ¬q) ∨ (p ∧ ¬r) ∨ (q ∨ r) demorgans law + double negation I'm stuck on…
shim
  • 23
  • 1
  • 3
2
votes
0 answers

as strong as = equivalent to?

In research articles in logic one can sometimes find claims such as the following: the proposition X is (logically) stronger than the proposition Y. For instance, P & Q can be said to be stronger than P because P & Q entails P, but not the other way…
Mijito
  • 235
2
votes
2 answers

Negation of specific statement

Definition: We say that $X\subset \mathbb{R}$ is bounded above if $\exists C\in \mathbb{R}$ s.t. $\forall x\in X$ we have $x\leq C$. $(X \ \text{is bounded above}):=\exists C\in \mathbb{R}((\forall x\in X)\Rightarrow (x\leq C))$ So I want to take…
RFZ
  • 16,814
2
votes
2 answers

A formula satisfiable from an infinite sequence of formulas

Let $\lbrace\varphi_n\rbrace_{n\geq 1}$ be a sequence of semantically inequivalent formulas s.t. $\vDash \varphi_{n+1} \to \varphi_{n}$. Is there a formula $\psi$ s.t. $(\lbrace\varphi_n\rbrace_{n\geq 1}\vDash \psi) \land (\forall n\geq…
gbi1977
  • 389
2
votes
2 answers

Trouble understanding statements using semantic consequence despite knowing the definition

I know semantic consequence to mean that all statements on the left can all be true (are satisfiable) if the right side is true. If the right side is false, than the statements on the left cannot all be true. There are a few statements giving me…
John Glen
  • 185
2
votes
0 answers

Karnaugh maps for resolution in propositional logic

Are Karnaugh maps "good enough" or mathematically acceptable to prove a CNF formula can't be satisfied instead of using propositional logic resolution? This method also shows all possibilities to satisfy the formula if there are any. Picture…
Andrej
  • 51
2
votes
1 answer

How do I simplify (SA ∧SB ∧SC)→(B∧¬A∧¬C)?

It is given that $SA = B \land \neg C$ $SB =A \to C$ $SC = \neg C \land (A \lor B)$ How do I get $(SA \land SB \land SC) \to (B \land \neg A \land \neg C)$? I did this (below) but now I'm stuck. $$B \land \neg C \land A \to C \land \neg C \land…
llamaro25
  • 289
2
votes
1 answer

How to prove that these propositions show that $f$ is injective?

Let $f$ be a total function on some nonempty set $D$. In the following propositions, x and y are variables ranging over $D$, and g is a variable ranging over total functions on $D$. Indicate all of the propositions that are equivalent to the…
M. Roshid
  • 69
  • 3