New answers tagged propositional-calculus
0
votes
Prove that [(p ∨ q) ∧ (p → s) ∧ (q → t)] → (s ∨ t) without using truth tables. What is the proof technique used?
This is the propositional form of a derived inference rule which is known as constructive dilemma or separation of cases.
It is actually a disjunction of two modus ponens statements (hence, the name '...
- 2,561
1
vote
Simplify, equivalent for $p \land(p\implies q)\land(p\implies\lnot q)$
$$p \land [(p \Rightarrow q) \land (p \Rightarrow \lnot q)] \\
p \land [(\lnot p \lor q) \land (\lnot p \lor \lnot q)] \\
p \land [\lnot p \land (q \lor \lnot q)] \\
p \land (\lnot p \land T) \\
p \...
- 24.6k
0
votes
Simplify, equivalent for $p \land(p\implies q)\land(p\implies\lnot q)$
Let $(P) : p \land (p \implies q) \land (p \implies \overline{q}) $ It is equivalent to : $$p \land (q \lor \overline{p}) \land (\overline{q} \lor \overline{p}) $$
Also equivalent to $$[p \land (q \...
3
votes
Simplify, equivalent for $p \land(p\implies q)\land(p\implies\lnot q)$
Make a truth table.
p
q
(p → q)
p ∧ (p → q)
(p → ¬q)
p ∧ (p → q) ∧ (p → ¬q)
T
T
T
T
F
F
T
F
F
F
T
F
F
T
T
F
T
F
F
F
T
F
T
F
So your expression is false all the time. Answer is $\boxed{F}$.
- 31
0
votes
An example of a maximal consistent set?
You can build a maximally consistent set of formulas as $\Sigma = \{ \psi \mid v(\psi) = T\}$ where $v$ is a truth assignment and $\psi$ is a formula of propositional logic.
$\Sigma$ is satisfiable ...
- 163
2
votes
Accepted
Is it not possible to model injective functions using propositional logic?
You're right, this is an application of the compactness theorem.
Suppose $S$ is a propositional theory whose models are exactly the $v$ such that $f_v$ is an injective function $X\to Y$.
Now fix $x\in ...
- 80.3k
0
votes
Is $C \to \neg C$ a "proper statement"?
Let $D$ stand for "It is dry." It stumps me that $D \to \neg D\tag1$ is a contingent sentence. This sentence seems always false. If anything it seems to be an obvious contradiction by logic ...
- 40.6k
0
votes
How would I prove the sequent $p \vee q, q \vee r, p \rightarrow \neg r \vdash q$ using natural deduction rules?
Your rules are for introduction and elimination of various connectives.
Your premises are two disjunctions and a conditional statement, the later which also contains a negation.
Your conclusion is an ...
- 131k
1
vote
Counter example in logics
There is no need to introduce $p,q,$ or $r$ when $\alpha,\beta,$ and $\delta$ are already doing that job.
All you need are examples for $\Gamma$ and $\Delta$ where:
$ \Delta\models\alpha$ and $\Gamma\...
- 131k
1
vote
The prenex form doesn't seem equivalent to the original sentence
$∀x\Big(∀y f(y) → g(x)\Big)\tag{A1}$
for all x, if for all y, f(y) is true, then g(x) is true
$∀x∃y\Big(f(y) → g(x)\Big)\tag{A2}$
...
- 40.6k
0
votes
Do De Morgan's laws hold in propositional intuitionistic logic?
This is basically the counterexample of that excellent answer, put a bit more abstractly.
Choose a Boolean algebra $B$ that has elements besides $0$ and $1$. Define $A=B\cup\{\star\}$ with $\star$ ...
- 6,645
2
votes
Where I am going wrong in translating this sentence from natural language to logical symbols?
Your answer was $$(\lnot s \land w) \implies d.$$
Recalling that $p \implies q$ is equivalent to $\lnot p \lor q$, and also recalling de Morgan's laws, your answer is equivalent to
$$ (s \lor \lnot w) ...
- 101k
0
votes
Is every argument with false premises and conclusion valid?
Is every argument with false premises and conclusion valid?
can an argument still be valid even if the premises and conclusion are all false?
An argument with a false premise and false conclusion ...
- 40.6k
0
votes
When is an implication true?
Further to the OP's comments under hmakholm's answer:
I just wanted to clarify when a statement p implies q is true - the implication is false if there can be true p and false q, even though we can ...
- 40.6k
0
votes
Need clarification on what makes an argument invalid or valid
$5$ is not an even number.
If $5$ is an even number, then $7$ is an even number.
$\therefore\quad 7$ is not an even number.
the hypotheses and conclusion are all true, so isn't the argument ...
- 40.6k
1
vote
Meta-logic of Hilbert-style propositional calculus
Basically, we have two methods in logic to specify an axiomatic system:
Either we enumerate axioms and inference rules, defining uniform/simultaneous substitution as a syntactic rule or a metatheorem; ...
- 2,561
0
votes
Proof of the principle of explosion
you are making the mistake that you allready assume classical (two valued) logic,
logic is just more than that .
in some logics $\lnot P \to Q \equiv P \lor Q$ is just not true. and in some ...
- 87
0
votes
Proof of the principle of explosion
this proof specifically deals with contradictions, not any false proposition;
The proof deals with when both a proposition and its negation are assumed true.
I could prove the same thing using the ...
- 131k
0
votes
Proof of the principle of explosion
I think your main confusion is that you seem to think that explosion only works when you have a contradictory proposition $P$. Note if $P$ is logically inconsistent, then $P \to Q$ is valid. This is a ...
- 1,444
1
vote
Accepted
How can a problem with cases be represented formally?
Naïm Favier's comment is spot-on.
First: A person who always tells the truth is called a "knight". It's quicker to say and to understand "$A$ is a knight" than to say or ...
-5
votes
Proof of the principle of explosion
The "proof" of POE given above is unfinished as neither premise has been discharged. We want to prove that if $P$ is true, then the implication $\neg P \implies Q$ must also be true for any ...
- 14.9k
2
votes
Proof of the principle of explosion
Re the second point in your question, the proof still holds.
We have (1) $P$ and (2) $¬P$ as assumptions.
Instead of deriving (3) $P \lor Q$ from (1) by Disjunction introduction (aka: Addition), we ...
- 95.3k
5
votes
Strong Completenss vs Finitely Strong Completenss
The canonical example of this is the logic $L(Q)$ gotten by adding the quantifier $Q\equiv$ "There exist uncountably many" to first-order logic. Improving on earlier work of Vaught, Keisler ...
- 251k
4
votes
Simplifying $(p\vee\neg q)\wedge(q\vee\neg r)\wedge(r\vee\neg p)$
Knowing that for each $a,b,c$
$$(a\lor b)\land c\equiv(a\land c)\lor(b\land c)$$
you may transform the first two terms as
$$\begin{align}
(p\lor\lnot q)\land(q\lor\lnot r) & \equiv ((p\lor\lnot q)\...
- 13.3k
0
votes
Simplifying $(p\vee\neg q)\wedge(q\vee\neg r)\wedge(r\vee\neg p)$
When I look at the propositions as Venn diagrams, it looks like you're saying that you need the inside of a Venn diagram OR the outside of another one, and this for all three Venn diagrams.
The result ...
- 2,868
1
vote
Notation for equivalent equations
What is the notation for showing that equations are equivalent after rearranging terms?
For example,
$$s=r\theta\implies r=\frac{s}{\theta}.\tag{✘ 1}$$
Is this the correct way to write it?
Consider ...
- 40.6k
0
votes
Proving $\vdash \neg \neg P \to P$ (double negation elimination) in first order logic, preferrably without deduction theorem
Minimal proof (17 steps)
You're asking for *2.14 from Metamath's pmproofs.txt database, which has a condensed detachment proof DD2DD2D13DD2D1311 in D-notation (that ...
- 282
0
votes
What does 'imply' mean in maths?
I'm not sure we need another answer here. But most of the other answers follow classical logic closely. I think the constructive logic meaning may be more intuitive. It's simply:
We say that $A$ ...
0
votes
What does 'imply' mean in maths?
Adding to the other answers (which have pointed out that $\boldsymbol P$ implies $\boldsymbol Q$ means that $P$ being true necessitates that $Q$ be true):
When we know that $\boldsymbol P$ is false ...
- 40.6k
0
votes
What does 'imply' mean in maths?
It means the same as it means in regular English. If we say “A implies B”, it means that the truth of B is a consequence of the truth of A.
There are many different ways of expressing this. For ...
- 43.8k
0
votes
Substitution principle for hypothetical judgements
I shall provide an interim, but I hope, workable enough answer, later to be replaced with a permanent one.
Discharging a hypothesis is essentially to relieve a formula of its function as a hypothesis ...
- 2,561
0
votes
Is "Alice loves candies" actually necessary for "Alice loves all sweet foods"?
The English-language statement "Alice loves candies" may either be taken to imply that Alice loves all candies, that Alice loves at least some candies, or most typically that Alice loves ...
- 563
6
votes
Is "Alice loves candies" actually necessary for "Alice loves all sweet foods"?
It seems like the analysis is made more complicated by thinking about negations.
More simply, consider the implication $B \implies A$; that is, "If Alice loves all sweet foods, then Alice loves ...
- 8,668
12
votes
Accepted
Is "Alice loves candies" actually necessary for "Alice loves all sweet foods"?
Your mistake is that for $A$ to be a necessary condition for $B$ it must hold that $\neg A\Rightarrow\neg B$ (if the necessary condition is not met, then the condition for which it is necessary is ...
- 14.5k
1
vote
Is "Alice loves candies" actually necessary for "Alice loves all sweet foods"?
A:Alice loves candies.
B:Alice loves all sweet foods.
I am trying to identify if A is a logically necessary condition (LNC) for B.
the answer key says that A is a ...
- 40.6k
0
votes
How to make a formal proof with A → (B ∨ C) ⊢ (A → B) ∨ (A → C)
what about to use a truth table?
1
vote
Are these two statements the same statement under the given constraints?
QUESTION: Under the bulleted constraints, are statements 1 and 2 equivalent?
Property 4 implies Properties 1 and 2,
Property 3 is defined only on functions that already satisfy Property 1.
$(f\in ...
- 40.6k
1
vote
Accepted
Are these two statements the same statement under the given constraints?
Well... kind of, but not really. For an analogy, suppose I made the following statement:
"If $\frac{0}{x} = 0$, then $x \neq 0$."
In some sense one could claim this is true: if "$\frac{...
- 6,679
1
vote
Did Jim Carrey get away with lying in 'Liar Liar'?
Since imperatives like "write it" and "write a poem" don't have truth values (regardless of whether they are obeyed, and of the ambiguity of "it"), they are not ...
- 40.6k
Top 50 recent answers are included