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

How would I do a derivation of this: ¬q→(q↔r), ¬q∧(p∨r) ⊢ p using inference rules?

I'm having a lot of trouble figuring out how to construct a derivation of ¬q→(q↔r), ¬q∧(p∨r) ⊢ p So far I've used conjunction elimination to get (p∨r) but then this is where I get stuck. I'm supposed to use disjunction elimination to get to p…
aqw143
  • 113
0
votes
2 answers

What is "not needing modus ponens"?

I am reading Rosser's Logic for Mathematicians, here ($P \supset Q$ means $P \rightarrow Q$): If we have $P \supset Q$ and $P$ proved, how come we have $Q$ without having to use modus ponens? It's as If for such occasion, there are two ways. It's…
Red Banana
  • 23,956
  • 20
  • 91
  • 192
0
votes
2 answers

How do I simplify $p \lor ((p \lor ¬q) \land (q \lor\neg r)) \lor \neg q \lor r$ using logical rules?

I'm trying to use the De Morgan and other rules of simplification but I'm going nowhere. Is this supposed to be hard or am I missing something?
0
votes
1 answer
0
votes
3 answers

Propositional logic: WFF of "neither A nor B"

In propositional logic, how should the sentence "neither A nor B" be converted into a Well Formed Formula? Is it $\sim(A \lor B)$ or should it be $\sim(A \land B)$? Can it be interrupted both ways? I need a little help understanding this.
mp27
  • 3
0
votes
1 answer

Notation for tautology, inconsistency and contingency

A tautology can be indicated like so: $\models \phi$ What is the notation for an inconsistency? $\not \models \phi$? What is the notation for a contingency?
Fabian
  • 3
0
votes
2 answers

determine whether ¬(p∨¬(p→q))∨p is a tautology by using laws of logic.

¬(p ∨ ¬(p→q)) ∨ p ≡ ¬(p ∨ ¬(¬p ∨ q) ∨p (implication rule) ≡ ¬(p ∨(p ∨ ¬q) ∨p (double negation rule) ≡ ¬(p ∨ p) ∨ ¬q) ∨p (associative rule) ≡ ¬((p ∨ ¬q)∨p (Idempotent rule) ≡ (¬p…
0
votes
3 answers

Is this a valid inference in propositional logic?

As part of a proof I have $\vdash p \to (q \to r)$. Can I from this infer $\vdash (p \wedge q) \to r$? It "feels" correct, but I can't seem to find a proof. Thanks for any help.
Nyaya
  • 51
0
votes
0 answers

If the prime interest rate goes up, then it is sufficient that unemployment goes down for prices to rise

I need an appropriate proposition for the following statement: If the prime interest rate goes up, then it is sufficient that unemployment goes down for prices to rise. With $p=$ prime interest rate goes up, $q=$ unemployment goes down and $r=$…
0
votes
1 answer

Determine $H_2$ according to the interpretation of $P$

$$ H_2 = ((P\to Q)\to(((P\land Q)\leftrightarrow P)\land((P\lor Q)\leftrightarrow Q)))\to P $$ The answer is $I[H_2]=0$, when $I[P] = 0$ I tried to do, but in my work I conclude that it depends on the interpretation of $Q$, $P$ is not sufficient to…
Goun2
  • 637
0
votes
1 answer

What are some general ways to design a propositional formula representing a function?

In my discrete math course we learned that when f is a finite function then there is a formula F in propositional logic such that: F(x,y) is true iff f(x)=y My question is, how do I construct such formula, other than some heuristic methods? In…
0
votes
1 answer

Axiomatized Formal Theory

T is an axiomatized formal theory whose wff's are constructed from "p", "q", and "r" and the familiar propositional connectives, and whose underlying logic is the standard propositional deduction system. The theory has the following…
0
votes
1 answer

How do I reconcile this truth table with the definition?

The circle and highlighted line confused me (logically, because I get the main idea) so I made a truth table, letting $P = x \notin A$ and $Q = x \in A ^\mathsf{c}$. Every truth assignment made sense except $P = F$, $Q = T$. If $P$ is false, is $x…
0
votes
1 answer

For logical equivalences involving conditionals/biconditionals here, do we need to prove some of them?

So I was wondering for logical equivalences involving conditionals/biconditionals mentioned here, do we need to use some of them as base and prove the rest using them or we just take them all as accepted, for example in case of equivalences…
Pooria
  • 477
0
votes
0 answers

Propositional Logic proof of $\land$ and $\lor$

I am trying to work out some basic logic stuff and currently am working with this, given 1 unary operator, denoted $\neg$ and one binary, denoted $\implies$, with the following rules given $$\neg\neg a=a$$ $$a\implies b = \neg b\implies \neg…
Zelos Malum
  • 6,570