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).
4,524
questions
0
votes
0answers
26 views
How to show that a valid rule is not derivable in intuitionistic propositional calculus.
First a word on notation, let the following be an inference rule that takes $\Gamma$ (a set of well-formed formulas) as premises and has $\psi$ (a well-formed formula) as a conclusion.
This is ...
0
votes
1answer
22 views
Expressing “For every positive integer $a$, there exists an integer $b$ with $|b| < a$ such that $|bx| < a$ for every real number $x$” symbolically
I would like to express
For every positive integer $a$, there exists an integer $b$ with $|b| < a$ such that $|bx| < a$ for every real number $x$
symbolically. My attempt:
For every positive ...
0
votes
1answer
24 views
How can I know when to negate quantifiers when taking the contrapositive of a statement?
Continued from a question I asked here, since I believed this question deserves its own thread.
When taking the contrapositive, I was taught to negate the quantifiers as well. For example, if we have ...
-1
votes
1answer
26 views
Contrapositive of: If $a$ is a real number such that $|a| < r$ for every positive real number $r$, then $a=0.$
I wish to state the contrapositive of:
If $a$ is a real number such that $|a| < r$ for every positive real number $r$, then $a=0.$
First, I want to state the original statement symbolically.
$\...
2
votes
1answer
62 views
Is disjunction elimination a more general form of modus ponens?
It seems to me that disjunction introduction and disjunction elimination implies modus ponens. To be clear, I'm defining disjunction introduction as:
$$p\vdash (p\lor q)$$
disjunction elimination as:
$...
2
votes
1answer
50 views
For $x \in \Bbb R$, for all $y (|y|<x \implies y<5)$
Given that $x$ is a free variable beloging to the set of real numbers, find the set of values for $x$ for which the following statement is true:
$\forall y (|y|<x \implies y<5)$
My attempt:
If $...
2
votes
1answer
60 views
Contrapositive of: If $a_n > 0$ and $\sum a_n$ converges, then $\sum 1/a_n$ diverges.
I would like to find the contrapositive of: If $a_n > 0$ and $\sum a_n$ converges, then $\sum 1/a_n$ diverges.
My first idea is to rewrite it symbolically: Let $a_n$ be a sequence of real numbers. $...
0
votes
0answers
30 views
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:
...
0
votes
1answer
16 views
resolvent clause theory
This is about correctness of resolution lemma
Let R be a resolvent of two clauses $C_1$ and $C_2$. Then $C_1, C_2 \models R$.
Proof By definition $R = (C_1 ā \{L\}) \cup (C_2 ā\{\bar{L}\}) $ (for some ...
-4
votes
0answers
36 views
Simplify $¬¬qā§T$ to get $q$. [closed]
I am having issues understanding how to use the laws of propositional logic.
Simplify $¬¬qā§T$ to get $q$.
-4
votes
1answer
26 views
Negation of $(p\to\neg q)ā§\neg p$ [closed]
can someone please help me out with the negation of the following:
$(p\to\neg q)ā§\neg p$
I keep getting confused at mid-way, so I'd appreciate a step-by-step approach.
Thanks!
1
vote
1answer
52 views
Using Truth Tables to Solve Logic Riddles
I've been traversing the practice exercises in Kenneth Rosen's Discrete Math and Its Applications in preparation for an upcoming class that is heavily proofs-based.
Constructing truth tables from ...
0
votes
3answers
35 views
Simple Logical Simplification - Distributive Law
I can't seem to understand the hopefully simple step of getting from :
$(a \land b \land c) \lor (a \land b \land \lnot c)$
to:
$(a \land b) \land (c \lor \lnot c)$
This step is in the answers and ...
0
votes
1answer
30 views
How to prove that propositions are not logically entailed?
Let's consider the next proposition: AāBāØAāØB
I used a truth table to show that there exists model1={A=False, B=False} where (AāB) is True but (AāØB) is False. It means AāB does Not entail AāØB.
Can you ...
0
votes
1answer
25 views
Does (A and B) entails (A if and only if B) and what is intuition?
Is the next statement correct: (Aā§B)āØ(AāB) ?
Formal definition of entailment is this: αāØĪ² if and only if, in every model in which α is true, β is also true.
I used a truth table to show that there is ...
0
votes
1answer
45 views
A small question concerning the correctness of induction
I think I've read enough about the Peano axioms and I also checked the similar posts here on StackExchange, but all I want to know is why induction can't be validated for all n by writing down the ...
2
votes
1answer
37 views
Is this a correct translation from english into symbolic logic? [duplicate]
"You can fool some of the people all of the time, and you can fool all of the people some of the time, but you canāt fool all of the people all of the time." (Abraham Lincoln)
Let
$P$ be &...
1
vote
1answer
33 views
Choice of postulate 1b in Kleene's Introduction to Metamathematics
In Introduction to Metamathematics, Kleene introduces a formal system where the first three postulates in the group for propositional calculus are:
$$
1a. A \to (B \to A)\\
1b. (A \to B) \to ((A \to (...
2
votes
2answers
37 views
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\...
0
votes
1answer
36 views
An element is either in a set or not in a set
Is there a name for the following obvious fact?
Given any set $S$ and any object $s$, either $s \in S$ or $s \notin S$.
4
votes
2answers
112 views
Prove that a wff built up only with $\lnot$ and $\leftrightarrow$ is a tautology iff $\lnot$ and each statement letter occur an even number of times.
First of all, I know how to prove this theorem below:
A statement form that contains $\leftrightarrow$ as its only connectives is a tautology iff each statement letter occurs an even number of times....
1
vote
1answer
54 views
How can something true follow from a false proposition? [duplicate]
Trying to wrap my head around conditional statements/implication and the respective truthtable in propositional logic. Read a number of the related posts on here. I understand that there is no causal ...
0
votes
1answer
90 views
Proving that $\mathscr B$ is a tautology iff $\lnot \mathscr B'$ is a tautology using induction.
I have the following logic question about duality:(Introduction to mathmatical Logic by elliot mendelson , exercise $1.30$)
If $\mathscr B$ is a statement form involving only $\lnot$ , $\land$, and $\...
0
votes
1answer
32 views
Clarification of a logical deduction example
I would like to ask for some clarification on an assignment of logical deduction. Specifically, the question is Which of the following are logically correct deductions? and below is an example:
If an ...
2
votes
0answers
59 views
Showing that $\mathscr B$ is a tautology iff $\lnot \mathscr B'$ is a tautology.
I have the following logic question about duality:(Introduction to mathmatical Logic by elliot mendelson , exercise $1.30$)
If $\mathscr B$ is a statement form involving only $\lnot$ , $\land$, and $\...
0
votes
2answers
50 views
Not understanding the meaning of a logic question.
I am trying to understand the meaning of this exercise question in a logic textbook.
For each of the following statement forms,find a statement form that is logically equivalent to its negation and ...
6
votes
1answer
194 views
Is XOR-SAT + $2$-SAT in P?
I read in a paper a proof where you can reduce a $3$-SAT problem into $2$-SAT + HORN-SAT clauses.
$2$-SAT + HORN-SAT is therefore, NP-complete.
$2$-SAT, HORN-SAT, DUAL HORN-SAT, XOR-SAT are all in P.
...
-2
votes
0answers
19 views
find a proposition f that makes the s tautology
i) s= ((f ā§ q) ā ¬p) ā ((p ā ¬q) ā f)
ii) s = ((r ā (¬qā§p)) ā f) ā (fā§(p ā q)ā§r).
started using DNF, select the solutions where s=t, and then get DNF for f only for these rows. Is this ok?
-1
votes
0answers
38 views
Can not verify the steps of this proof following the laws at each step
I am reading a proof structure of showing that ~true = false
It is based on the laws of negation i.e. ~p = p = false
Please note ...
0
votes
1answer
26 views
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 ...
0
votes
3answers
43 views
How to simplify $(\lnot p \rightarrow \lnot q) \land p$ and match the right statement?
The problem is as follows:
"If Maria does not leave her house then she does not catch a cold, but Maria leaves her house" is equivalent to:
I. Maria does not leave her house.
II. It is not ...
-3
votes
1answer
41 views
If $[(p\rightarrow\ q)\land (\lnot p \rightarrow \lnot r)]\rightarrow (\lnot q \rightarrow r)$ is false how to find its equivalent in other words?
The problem is as follows:
Assume the statement which is written below is false,
...
-1
votes
1answer
46 views
How to establish the truth values of a set of statements which depend on $\lnot p \rightarrow (q\lor \lnot r)$ when its false?
The problem is as follows:
First find the truth values of $p$, $q$ and $r$ such as the complex statement from below is false.
$$\lnot p \rightarrow (q\lor \lnot r)$$
Then using this information find ...
0
votes
1answer
88 views
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-...
0
votes
2answers
56 views
How to find the profit earned from getting right a set of logic statements?
The problem is as follows:
Diana offers her sister Maria $3$ bitcoins for each true statement and $4$ bitcoins for each false that she finds correctly in the statements shown, where $\mathbb{Z}$ is ...
2
votes
1answer
36 views
Simplifying $[\{(\lnot p\lor q)\land(\lnot q\lor p)\}\to\{(q\lor\lnot p)\land p\}]\to[(p \leftrightarrow q)\lor(q \bigtriangleup p)]$
Simplify the following expression:
$$\left[\{(\lnot p \lor q)\land(\lnot q \lor p)\}\rightarrow\{(q \lor \lnot p)\land p\}\right]\rightarrow\left[(p \leftrightarrow q)\lor(q \bigtriangleup p)\right]$$
...
2
votes
2answers
28 views
Intuitive logic behind the following equivalences in propositional logic
I was going through the text Discrete mathematics and its applications by Kenneth H. Rosen where I came across few logical equivalences as follows:
$1. (pāq)ā§(pār)ā”pā(qā§r)$
$2. (pār)ā§(qār)ā”(pāØq)ār$
$...
1
vote
1answer
29 views
Can an assumption be discharged without it being part of the tree?
Given the following formula, use natural deduction to prove that it holds.
The answer given by the professor was the following below:
I would like to understand how we can discharge the assumption ...
0
votes
0answers
23 views
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)\...
2
votes
1answer
46 views
What Percentage of Formulas in Propositional Logic is Satisfiable?
Let $P_{n}$ be the set of all formulas in propositional logic with $n$ variables. Let then $Q_{n} \subset P_{n}$ be the maximal set of all non-equivalent formulas in propositional logic of length $n$.
...
2
votes
1answer
29 views
Prove that {A ā ¬C, ¬A ā B} ⢠C ā B using only Modus Ponens, the typical theorem (A ā ¬C) ā (C ā ¬A) and 3 axioms.
I have an exercise where I have to prove the given sentence
{A ā ¬C, ¬A ā B} ⢠C ā B using only Modus Ponens, the typical theorem (A ā ¬C) ā (C ā ¬A)
and the following three axioms:
Aā(BāA)
(Aā(BāC))ā...
0
votes
1answer
73 views
Sum of symbol values in wff written in polish notation.
So I am currently dealing with a problem like this:
If we count $\rightarrow , \land , \lor$ and $\leftrightarrow$ each as $+1$ , each statement letter as $-1$ and $\lnot$ as $0$ , prove that an ...
3
votes
0answers
57 views
Reasoning about “implies” truth table. [duplicate]
I am trying to find a reasoning for the truth table of $A \rightarrow B$ .Here is what I came to so far.
$1.$ We have to first assume that if something can't be proven wrong , then it is true.
$2.$ $A ...
-1
votes
0answers
39 views
How to find an atom which is not in a countably infinite set?
Suppose that a countably infinite list of propositional atoms $\mathcal{A}$. The resulting logical language is denoted $\mathcal{L}$. We write $K$ for a countably infinite set of formulas over $\...
1
vote
1answer
49 views
Prove “If $\{R, Q\} \vDash P$, then $¬P \vdash \lnot Q \lor \lnot R$”.
Using the book Dirk van Dalen. "Logic and Structure (Universitext)" as reference text.
Decide whether the following statement is true or false, justifying the answer.
If $\{R, Q\} \vDash P$,...
0
votes
0answers
57 views
Confusion about restoration of parenthesis.
In "Introduction to Mathematical Logic" by Elliot Mendelson , page $11-12$ , There is a passage about the restoration of parenthesis . As a example:
$1. B \rightarrow \lnot\lnot A$
$2. B \...
1
vote
1answer
31 views
proof pierce law using contradiction [duplicate]
how to proof pierce law using contradiction
$((a -> b) -> a) -> a$ ?
$((a -> b) -> a) -> ~a$
$((a \lor a) \land (\neg b \lor a) -> \neg a$
please help pierce law proof using ...
0
votes
0answers
32 views
Logic question with premises
Put the following syllogism into the standard form, which uses a horizontal line to separate premises and conclusion. Moreover, tell whether it is valid or not by showing its Venn Diagram.
Bill didn't ...
-2
votes
1answer
44 views
Having problems this proof [closed]
Suppose that $\phi$ proves if $\alpha$ then $\neg\beta$ and that $\phi$ proves $\beta$. Can we infer anything from $\phi$?
0
votes
0answers
7 views
Proof techniques for Åukasiewicz's propositional axioms {CCpqCCqrCpr, CCNppp, CpCNpq}
When I learned propositional calculus in school I was taught Åukasiewicz's third axiom system (https://en.wikipedia.org/wiki/List_of_Hilbert_systems#cite_ref-Pro_I_1-2):
$$a ā b ā a$$
$$(a ā b ā c) ā (...