What you might not be remembering is that friction is affected by surface area. Partial deflation of the tire increases the surface area of the contact patch.
Actually no. The classic physics formula for friction is independent of surface area. Given the same normal force and the same coefficient of friction, the frictional force is the same no matter what the surface area.
The reason that deflating tires helps traction is that in materials like snow and soft sand, distributing the load over a bigger area actually
changes the coefficient of friction because the snow/sand is less compacted. See
Friction and Normal Force