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

I'm having some trouble in the below propositional logic question.

How to write the statement for the following? If it does not rain, then if we go swimming then we have to take the bus. I have been confused with the above "then" repetition...
0
votes
4 answers

How to prove that $(p \land (\neg(\neg p \lor q))) \lor (p \land q) \equiv p$?

My attempt at this mathematical demonstration was as follows: (p ∧ (¬(¬p ∨ q))) ∨ (p ∧ q) ≡ p ≡ (p ∧ (p ∨ q) ∨ (p ∧ q) ≡ ((p ∨ p) ∧ q) ∨ (p ∧ q) ≡ ((p ∨ p) ∧ q) ∨ (p ∧ q) ≡ (p ∧ q) ∨ (p ∧ q) ≡ p
0
votes
0 answers

Is the proposition "There are 4 regular solids" true or false

I am currently learning about propositions and came across a statement in this video: There are 5 regular solids: true There are 6 regular solids: false But then I am wondering if a statement There are 4 regular solids will be considered true or…
senseiwu
  • 214
0
votes
1 answer

How is the negation operator a connective?

While going through a lot of notes online on propositional logic, I've come to the conclusion that people generally refer to the $\neg$ (negation) operator as a connective. However, strictly speaking, I think that a connective is any operator that…
coderboy
  • 113
0
votes
0 answers

Are there "Independence-friendly" variants of propositional calculi?

Have propositional calculi with independence-related features been named and studied? Are they trivial as logical systems? Are there any interesting properties that they either gain or lose relative to ordinary propositional…
Greg Nisbet
  • 11,657
0
votes
0 answers

How does a negation distribute when a statement is expressed in words?

Consider the following implication: Let $x,y,z$ be integers. If exactly two of the three integers $x,y,z$ are even, then $3x + 5y + 7z$ is odd. The contrapositive of the statement above would be: Let $x,y,z$ be integers. If not ($3x + 5y + 7z$ is…
0
votes
1 answer

Solution without truth tables

Find all the estimations that show that the following is false. $(x \land y)\lor (x\land z)\lor(y\land z)\lor(u\land v)\lor (u\land w)\lor(v\land w)\lor(\neg x\land\neg u)$. I know how to solve this by using truth tables however, I need 64…
gav
  • 31
0
votes
1 answer

Connective symbol similar to implies, but acts like And

This feels like a basic question or a misunderstanding, but I'm struggling to identify a simple concept having to do with the provability of an argument or proof. Imagine you have a proof that is well-reasoned and believed true, but then you…
tunesmith
  • 231
0
votes
0 answers

stuck on logic and propositional calculus problem

1.Show that $\neg((\neg p\land q)\lor(\neg p\land \neg q))\lor(p\land q)\equiv p.$ $\neg((\neg p\land q)\lor(\neg p\land \neg q))\lor(p\land q)\equiv \neg(\neg p\land ( q\lor \neg q))\lor (p\land q)\equiv \neg(\neg p\land q)\lor (p\land q)\equiv…
Unknown
  • 3,073
0
votes
1 answer

if $p\implies q$ is the same as $\lnot p \lor q$, then...

If $p\implies q$ is the same as $\lnot p \lor q$, then what is $p\implies \lnot q$? I'm not sure if this is $\lnot p \lor \lnot q$, or $\lnot p \lor q$. I'm trying to figure this out, because i have a problem: ~(q v p) --> ~r). I use demorgans law…
Anteara
  • 163
0
votes
1 answer

Solve this logic problem, or justify why it can't be solved?

Five sticks (S1, S2, S3, S4 and S5) are placed next to each other, in a circular way so that S1 is next to S2, S2 is next to S3 and so on, and S5 is next to S1. The sticks need to be painted black or white, such that each stick can be only painted…
0
votes
0 answers

How do you show this is a contradiction?

The following statement is a contradiction: "We are happy, and it is not the case that Cole having ordered the pizza implies that we are happy." Express this statement in symbolic logic, clearly specifying what English statements any variables…
0
votes
3 answers

Why are these $2$ statements not logically equivalent?

This is my first post on this site. I am stuck on a logic question. The question states: which statements is/are logically equivalent to: Kimo will pass algebra I only if he studies. a) If kimo studies, then he will pass Algebra I b) either kimo…
xiao
  • 29
0
votes
2 answers

Equivalence of propositions $a\Leftrightarrow b$ and $(a\Rightarrow b)\wedge(\neg b\Rightarrow \neg a)$.

Is the statement $a\Leftrightarrow b$ equivalent to the statement $(a\Rightarrow b)\wedge(\neg b\Rightarrow \neg a)$? For example: "I get out if and only if it is sunny" should be equivalent to "When I get out, it's sunny. When it's not sunny, I…
0
votes
4 answers

Showing a propositional formula is a contradiction

Please help me with showing that the expression $P\land (Q\lor \neg P) \land \neg Q$ is a contradiction? Your help is greatly appreciated What I have tried so far: $$\begin{align*} &C = \text{contradiction}\\ &\Rightarrow P\land (Q\land \neg Q)…
user10695
  • 655